UVA_11996
这个题目前三个操作都是典型的splay的操作，但是第四个操作之前没见过，我以前只用字典树+二分求过任意两个串的LCP，但这次是在splay上便一时间无从下手。后来看了别人的代码发现也是基于二分的，而至于如何判断二分出来的前缀是相同的，则直接用哈希值去比较了。
至于直接用哈希值判断两个字符串是否相等，我一开始也觉得很不靠谱，后来分析了一下发现虽然不靠谱但不靠谱的概率是比较小的。假定我们用一个long long的哈希值，它可以区分出2^64个不同的字符串（当然这只是极限情况，如果哈希算法不同所能表示的字符串的数量也不大相同），而题目的01串至多也就400,000位，这样即便每个子串都不同也就才有1.6*10^11个，是远远小于2^64的，因此不同的子串出现同一个哈希值的概率微乎其微。
为了让同样的字符串能得到同样的哈希值，可以用对应位的值乘以x的对应次幂来计算哈希值，x选3、选7都能AC，至于选别的我没试过，但是一定别选2之类的，因为用long long存x的幂相当于自动mod2^64，这样后面的值就都是0了……在维护splay的同时维护好当前节点所表示的区间的哈希值就可以了，由于涉及到翻转的操作，可以选择维护两个哈希值，一个是正着算的，一个是倒着算的，当一个区间翻转时只要将这两个哈希值交换就可以了，而不必再重新计算。
#include<stdio.h> #include<string.h> #include<algorithm> #define MAXD 400010 typedef long long LL; int N, M, T, node; LL fac[MAXD]; struct Splay { int pre, ls, rs, key, size, rev; LL h[2]; void pushdown(); void update(); void zig(int x); void zag(int x); void splay(int x, int goal); void init() { pre = ls = rs = key = size = rev = h[0] = h[1] = 0; } }sp[MAXD]; inline void Rev(int cur) { if(cur) sp[cur].rev ^= 1, std::swap(sp[cur].h[0], sp[cur].h[1]); } inline void Splay::pushdown() { if(rev) { Rev(ls), Rev(rs); std::swap(ls, rs); rev = 0; } } inline void Splay::update() { size = sp[ls].size + sp[rs].size + 1; h[0] = sp[ls].h[0] * fac[sp[rs].size + 1] + key * fac[sp[rs].size] + sp[rs].h[0]; h[1] = sp[rs].h[1] * fac[sp[ls].size + 1] + key * fac[sp[ls].size] + sp[ls].h[1]; } void Splay::zig(int x) { int y = rs, fa = pre; rs = sp[y].ls, sp[rs].pre = x; sp[y].ls = x, pre = y; sp[y].pre = fa; if(fa == 0) T = y; else sp[fa].rs == x ? sp[fa].rs = y : sp[fa].ls = y; update(); } void Splay::zag(int x) { int y = ls, fa = pre; ls = sp[y].rs, sp[ls].pre = x; sp[y].rs = x, pre = y; sp[y].pre = fa; if(fa == 0) T = y; else sp[fa].rs == x ? sp[fa].rs = y : sp[fa].ls = y; update(); } void Splay::splay(int x, int goal) { int y, z; for(; pre != goal;) { y = pre; if(sp[y].pre == goal) sp[y].rs == x ? sp[y].zig(y) : sp[y].zag(y); else { z = sp[y].pre; if(sp[z].rs == y) { if(sp[y].rs == x) sp[z].zig(z), sp[y].zig(y); else sp[y].zag(y), sp[z].zig(z); } else { if(sp[y].ls == x) sp[z].zag(z), sp[y].zag(y); else sp[y].zig(y), sp[z].zag(z); } } } update(); } void Goto(int k, int goal) { int i = T, n; for(;;) { sp[i].pushdown(); n = sp[sp[i].ls].size; if(n + 1 == k) break; else if(k <= n) i = sp[i].ls; else i = sp[i].rs, k -= n + 1; } sp[i].splay(i, goal); } char b[MAXD]; void build(int &cur, int x, int y, int fa) { int mid = x + y >> 1; sp[mid].init(); cur = mid, sp[mid].pre = fa, sp[mid].key = b[mid] - '0'; if(x < mid) build(sp[mid].ls, x, mid - 1, mid); if(mid < y) build(sp[mid].rs, mid + 1, y, mid); sp[mid].update(); } void init() { scanf("%s", b + 1); sp[0].init(), sp[N + 1].init(), sp[N + 2].init(); T = N + 1, sp[N + 1].rs = N + 2, sp[N + 2].pre = N + 1; build(sp[N + 2].ls, 1, N, N + 2); sp[N + 2].update(), sp[N + 1].update(); node = N + 2; } void newnode(int &cur, int c) { cur = ++ node; sp[cur].init(), sp[cur].key = c; sp[cur].update(); } void insert(int x, int c) { Goto(x + 1, 0), Goto(x + 2, T); int cur = sp[T].rs; newnode(sp[cur].ls, c); sp[node].pre = cur; sp[cur].update(), sp[T].update(); } void remove(int x) { Goto(x, 0), Goto(x + 2, T); int cur = sp[T].rs; sp[cur].ls = 0; sp[cur].update(), sp[T].update(); } void reverse(int x, int y) { Goto(x, 0), Goto(y + 2, T); Rev(sp[sp[T].rs].ls); } int hash(int x, int y) { Goto(x, 0), Goto(y + 2, T); return sp[sp[sp[T].rs].ls].h[0]; } int common(int x, int y, int L) { return hash(x, x + L - 1) == hash(y, y + L - 1); } void LCP(int x, int y) { int min, mid, max, L = sp[T].size - 2; min = 0, max = std::min(L - x + 1, L - y + 1) + 1; for(;;) { mid = min + max >> 1; if(mid == min) break; if(common(x, y, mid)) min = mid; else max = mid; } printf("%d\n", mid); } void solve() { int i, op, x, y; for(i = 0; i < M; i ++) { scanf("%d", &op); if(op == 1) { scanf("%d%d", &x, &y); insert(x, y); } else if(op == 2) { scanf("%d", &x); remove(x); } else if(op == 3) { scanf("%d%d", &x, &y); reverse(x, y); } else { scanf("%d%d", &x, &y); LCP(x, y); } } } int main() { fac[0] = 1; for(int i = 1; i < MAXD; i ++) fac[i] = 7 * fac[i - 1]; // Choosing 7 is just as my like. while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0; }