[BZOJ1014] [JSOI2008]火星人prefix splay+字符串hash 重写版

看着去年十二月那个5K+的代码 我突然觉得过去的我还是蛮拼的

用Hash维护一棵子树的信息 更改和询问都比较方便可以参考原来的那篇

对于插入 其实应该找到把x-1旋转到根 x+1旋转到根的右儿子然后再插到x+1的做儿子处

感觉这样靠谱些 而且用数组版的splay代码少了好几K

但是还是跑了9s 慢的要死啊Orz

果然像我这样的人最好早点滚粗

#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#include<queue>#define SF scanf#define PF printfusing namespace std;typedef long long LL;const int MAXN = 150000;const int MOD = 199999;int base[MAXN+10];int n, m;char c;char s[MAXN+10];struct Splay_Tree{int val[MAXN+10], sz[MAXN+10], fa[MAXN+10];int RK[MAXN+10];int ncnt, root, ch[MAXN+10][2];void up(int x) {sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;RK[x] = (1LL * RK[ch[x][0]] * base[sz[ch[x][1]]+1] % MOD +1LL * val[x] * base[sz[ch[x][1]]] % MOD +RK[ch[x][1]]) % MOD;}void NewNode(int &x, int key, int pre) {x = ++ncnt;val[x] = key; sz[x] = 1; fa[x] = pre;ch[x][0] = ch[x][1] = 0;}void Rotate(int x) {int y = fa[x], z = fa[y];bool d = x == ch[y][0];if(ch[y][!d] = ch[x][d]) fa[ch[x][d]] = y;if(fa[x] = z) ch[z][y == ch[z][1]] = x;up(ch[x][d] = y); fa[y] = x;}void splay(int x, int goal) {for(int y = fa[x]; y ^ goal; Rotate(x), y = fa[x])if(fa[y] != goal) Rotate((x == ch[y][0]) && (y == ch[fa[y]][0]) ? y : x);up(x); if(!goal) root = x;}int Find_kth(int k) {int x = root;if(k < 0 || k > sz[x]) return -1;while(k <= sz[ch[x][0]] || k > sz[ch[x][0]] + 1)if(k <= sz[ch[x][0]]) x = ch[x][0];else k -= sz[ch[x][0]] + 1, x = ch[x][1];splay(x, 0); return x;}void Build(int &x, int l, int r, int pre) {if(l > r) return ;int mid = (l + r) >> 1;NewNode(x, s[mid], pre);Build(ch[x][0], l, mid-1, x);Build(ch[x][1], mid+1, r, x);up(x);}} sp;void init() {base[0] = 1;for(int i = 1; i <= MAXN; i++) base[i] = 1LL * base[i-1] * 28 % MOD;}int Find_RK(int x, int len) {int y = x + len – 1, a, b;a = sp.Find_kth(x-1);b = sp.Find_kth(y+1);sp.splay(a, 0); sp.splay(b, a);return sp.RK[sp.ch[b][0]];}bool check(int x, int y, int len) {int a = Find_RK(x, len);int b = Find_RK(y, len);return a == b;}void R(int x, int key) {int pos = sp.Find_kth(x);sp.splay(pos, 0); sp.val[pos] = key; sp.up(pos);}void I(int x, int key) {int a = sp.Find_kth(x), b = sp.Find_kth(x+1), cur;sp.splay(a, 0); sp.splay(b, a);sp.NewNode(cur, key, b); sp.ch[b][0] = cur;sp.up(cur); sp.up(b); sp.up(a);n++;}void Q(int x, int y) {int L = 1, R = min(n-x, n-y), ans = 0;while(L <= R) {int mid = (L + R + 1) >> 1;if(check(x, y, mid)) L = mid+1, ans = mid;else R = mid-1;}PF("%d\n", ans);}int main() {init();SF("%s", s+1);n = strlen(s+1);for(int i = 1; i <= n; i++) s[i] -= 'a';s[0] = s[n+1] = 27;sp.Build(sp.root, 0, n+1, 0);n += 2;SF("%d", &m);for(int i = 1; i <= m; i++) {int x, y;SF(" %c", &c);switch(c) {case 'R' :SF("%d", &x);if(x > n-2) continue ; x++;SF(" %c", &c);R(x, c-'a');break;case 'I' :SF("%d", &x); x++;SF(" %c", &c);I(x, c-'a');break;case 'Q' :SF("%d%d", &x, &y); x++; y++;Q(x, y);}}}

，我们摇摇头说，困难其实没什么大不了。