首页 > 代码库 > ACdream 1104 瑶瑶想找回文串（SplayTree + Hash + 二分）
ACdream 1104 瑶瑶想找回文串（SplayTree + Hash + 二分）
Problem Description
刚学完后缀数组求回文串的瑶瑶（tsyao）想到了另一个问题：如果能够对字符串做一些修改，怎么在每次询问时知道以某个字符为中心的最长回文串长度呢？因为瑶瑶整天只知道LOL，当他知道自己省选成绩的时候就天天在LOL，导致现在的她实在是太弱了，根本解决不了这个问题，于是就来找你帮忙，么么哒~你就帮帮她吗
Input
第一行为一个长度不超过100000字符串s作为初始字符串。第二行一个正整数n，表示操作/询问的个数。接下来n行，每行有如下几种可能出现的操作/询问：
Insert a x 在a处字符的后面插入一个字符x
Delete a 把a处字符删除
Update a x 把a处字符改为x
Query a 查询以a为中心的最长回文串长度
Output
对于每个询问，输出得到的最长回文串长度
题目大意：略。
思路：
——————————————————————————————————————————————————————————
搬一下官方（？）题解：http://tsyao.tk/archives/94
SPLAY保存改区间从左向右的hash值和从右向左的hash值，对于每个询问，二分字符串长度。总的时间复杂度是O(qlognlogn)
——————————————————————————————————————————————————————————
处理技巧：头尾加上一个空字符可以不用考虑边界的情况。
代码（1932MS）：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXN = 150010; 9 const int MOD = 1e8 + 7; 10 const LL seed = 131; 11 12 LL base[MAXN]; 13 char s[MAXN], op[10]; 14 int n, m; 15 16 void initBase(int n = 150000) { 17 base[0] = 1; 18 for(int i = 1; i <= n; ++i) base[i] = base[i - 1] * seed % MOD; 19 } 20 21 struct SplayTree { 22 struct Node { 23 int size, lhash, rhash; 24 char c; 25 Node *fa, *ch[2]; 26 }; 27 Node statePool[MAXN], *nil, *root; 28 int stk[MAXN], top; 29 int ncnt; 30 31 SplayTree() { 32 nil = statePool; 33 } 34 35 void init() { 36 ncnt = 1; 37 top = 0; 38 } 39 40 Node* new_node(char v, Node* f) { 41 Node* t; 42 if(top) t = &statePool[stk[--top]]; 43 else t = &statePool[ncnt++]; 44 t->size = 1; 45 t->lhash = t->rhash = t->c = v; 46 t->ch[0] = t->ch[1] = nil; 47 t->fa = f; 48 return t; 49 } 50 51 void del_node(Node* &x) { 52 stk[top++] = x - statePool; 53 x = nil; 54 } 55 56 void update(Node* x) { 57 int s0 = x->ch[0]->size, s1 = x->ch[1]->size; 58 x->size = s0 + s1 + 1; 59 x->lhash = (x->ch[0]->lhash * base[s1 + 1] + x->c * base[s1] + x->ch[1]->lhash) % MOD; 60 x->rhash = (x->ch[1]->rhash * base[s0 + 1] + x->c * base[s0] + x->ch[0]->rhash) % MOD; 61 } 62 63 void rotate(Node* x) { 64 Node* y = x->fa; 65 int t = (y->ch[1] == x); 66 y->fa->ch[y->fa->ch[1] == y] = x; x->fa = y->fa; 67 y->ch[t] = x->ch[t ^ 1]; x->ch[t ^ 1]->fa = y; 68 x->ch[t ^ 1] = y; y->fa = x; 69 update(y); 70 } 71 72 void splay(Node* x, Node* f) { 73 while(x->fa != f) { 74 if(x->fa->fa == f) rotate(x); 75 else { 76 Node *y = x->fa, *z = y->fa; 77 if((z->ch[1] == y) == (y->ch[1] == x)) rotate(y); 78 else rotate(x); 79 rotate(x); 80 } 81 } 82 update(x); 83 if(x->fa == nil) root = x; 84 } 85 86 Node* kth(int k) { 87 Node* x = root; 88 while(true) { 89 int t = x->ch[0]->size + 1; 90 if(t == k) break; 91 if(t > k) x = x->ch[0]; 92 else x = x->ch[1], k -= t; 93 } 94 return x; 95 } 96 97 void build(Node* &x, Node* f, int l, int r) { 98 int mid = (l + r) >> 1; 99 x = new_node(s[mid], f);100 if(l < mid) build(x->ch[0], x, l, mid - 1);101 if(mid < r) build(x->ch[1], x, mid + 1, r);102 update(x);103 }104 105 void insert(int pos, char c) {106 splay(kth(pos), nil);107 splay(kth(pos + 1), root);108 root->ch[1]->ch[0] = new_node(c, root->ch[1]);109 update(root->ch[1]); update(root);110 }111 112 void modify(int pos, char c) {113 splay(kth(pos), nil);114 root->c = c;115 update(root);116 }117 118 void remove(int pos) {119 splay(kth(pos - 1), nil);120 splay(kth(pos + 1), root);121 del_node(root->ch[1]->ch[0]);122 update(root->ch[1]); update(root);123 }124 125 bool check(int pos, int len) {126 splay(kth(pos - len - 1), nil);127 splay(kth(pos + len + 1), root);128 splay(kth(pos), root->ch[1]);129 Node* x = root->ch[1]->ch[0];130 return x->lhash == x->rhash;131 }132 133 int query(int pos) {134 int l = 1, r = min(pos - 2, root->size - 1 - pos) + 1;135 while(l < r) {136 int mid = (l + r) >> 1;137 if(check(pos, mid)) l = mid + 1;138 else r = mid;139 }140 return 2 * l - 1;141 }142 143 void debug(Node* x) {144 static int t = 0;145 if(x == root) printf("Debug %d\n", ++t);146 printf("val:%d lson:%d rson:%d lhash:%d rhash:%d\n", x - statePool, x->ch[0] - statePool, x->ch[1] - statePool, x->lhash, x->rhash);147 if(x->ch[0] != nil) debug(x->ch[0]);148 if(x->ch[1] != nil) debug(x->ch[1]);149 }150 } splay;151 152 int main() {153 scanf("%s", s + 1);154 n = strlen(s + 1);155 initBase();156 splay.init();157 splay.build(splay.root, splay.nil, 0, n + 1);158 scanf("%d", &m);159 char c;160 for(int i = 0, a; i < m; ++i) {161 scanf("%s%d", op, &a);162 ++a;163 if(strcmp(op, "Insert") == 0) {164 scanf(" %c", &c);165 splay.insert(a, c);166 }167 if(strcmp(op, "Delete") == 0)168 splay.remove(a);169 if(strcmp(op, "Update") == 0) {170 scanf(" %c", &c);171 splay.modify(a, c);172 }173 //splay.debug(splay.root);174 if(strcmp(op, "Query") == 0)175 printf("%d\n", splay.query(a));176 }177 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。