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
", ++t);
146         printf("val:%d lson:%d rson:%d lhash:%d rhash:%d
", 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
", splay.query(a));
176     }
177 }

View Code