嘟嘟嘟
嗯。
splay维护哈希。
如题，用splay维护哈希，查找的时候二分。所以复杂度是取决于询问复杂度：\(O(n \log^ 2{n})\)。
这道题还有一个技巧，就是一个节点记录的是他的子树的哈希值，所以树的的形态改变的同时，每一个节点记录的哈希值也在改变。在pushup的时候，应该这么写：\(t[now].has = t[l].has * base ^ {t[r].siz + 1} + (s[now] - ‘a‘) * base ^ {t[r].siz} + t[r].has\)。
然后好像就没什么好说的啦，各种操作的中心思想都是通过旋转前驱后继提取区间。
然后注意\(base\)别取字符集大小，我因为取了\(26\)导致大的点没过去，应该是取的太小导致冲突的概率比较大吧。
然而取\(27\)就过了～
#include<cstdio>#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<cstdlib>#include<cctype>#include<vector>#include<stack>#include<queue>using namespace std;#define enter puts("") #define space putchar(‘ ‘)#define Mem(a, x) memset(a, x, sizeof(a))#define rg registertypedef long long ll;typedef unsigned long long ull;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 1e5 + 5;inline ll read(){ ?ll ans = 0; ?char ch = getchar(), last = ‘ ‘; ?while(!isdigit(ch)) last = ch, ch = getchar(); ?while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar(); ?if(last == ‘-‘) ans = -ans; ?return ans;}inline void write(ll x){ ?if(x < 0) x = -x, putchar(‘-‘); ?if(x >= 10) write(x / 10); ?putchar(x % 10 + ‘0‘);}int m;ull p[maxn];char s[maxn], c[2], tp[2];struct Tree{ ?int ch[2], fa; ?int siz; ull has;}t[maxn];int root, ncnt = 0;void _PrintTr(int now){ ?if(!now) return; ?printf("nd:%d ls:%d rs:%d\n", now, t[now].ch[0], t[now].ch[1]); ?_PrintTr(t[now].ch[0]); _PrintTr(t[now].ch[1]);}void pushup(int now){ ?int l = t[now].ch[0], r = t[now].ch[1]; ?t[now].siz = t[l].siz + t[r].siz + 1; ?t[now].has = t[l].has * p[t[r].siz + 1] + (s[now] - ‘a‘) * p[t[r].siz] + t[r].has;}void rotate(int x){ ?int y = t[x].fa, z = t[y].fa, k = (t[y].ch[1] == x); ?t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z; ?t[y].ch[k] = t[x].ch[k ^ 1]; t[t[y].ch[k]].fa = y; ?t[x].ch[k ^ 1] = y; t[y].fa = x; ?pushup(y); pushup(x);}void splay(int x, int s){ ?while(t[x].fa != s) ???{ ?????int y = t[x].fa, z = t[y].fa; ?????if(z != s) ???{ ?????if((t[z].ch[0] == y) ^ (t[y].ch[0] == x)) rotate(x); ?????else rotate(y); ???} ?????rotate(x); ???} ?if(!s) root = x;}void build(int L, int R, int f){ ?if(L > R) return; ?int mid = (L + R) >> 1; ?if(L == R) t[L].siz = 1, t[L].has = s[L] - ‘a‘; ?else build(L, mid - 1, mid), build(mid + 1, R, mid); ?t[f].ch[mid > f] = mid; t[mid].fa = f; ?pushup(mid);}int rnk(int k){ ?int now = root; ?while(1) ???{ ?????if(k <= t[t[now].ch[0]].siz) now = t[now].ch[0]; ?????else if(k == t[t[now].ch[0]].siz + 1) return now; ?????else k -= (t[t[now].ch[0]].siz + 1), now = t[now].ch[1]; ???} }void update(int x){ ?int now = rnk(x); splay(now, 0); ?s[now] = tp[0]; ?pushup(now);}void insert(int x){ ?int a = rnk(x), b = rnk(x + 1); ?splay(a, 0); splay(b, a); ?s[++ncnt] = tp[0]; ?t[ncnt].has = tp[0] - ‘a‘; ?t[ncnt].siz = 1; ?t[ncnt].ch[0] = t[ncnt].ch[1] = 0; ?t[b].ch[0] = ncnt; t[ncnt].fa = b; ?pushup(b); pushup(a);}bool judge(int x, int y, int len){ ?if(x + len > ncnt || y + len > ncnt) return 0; ?int a = rnk(x - 1), b = rnk(x + len); ?splay(a, 0); splay(b, a); ?//_PrintTr(root); ?//puts("~~~~~~~~~~~~~~~~~~"); ?ull has1 = t[t[b].ch[0]].has; ?a = rnk(y - 1), b = rnk(y + len); ?splay(a, 0); splay(b, a); ?//_PrintTr(root); ?ull has2 = t[t[b].ch[0]].has; ?return has1 == has2;}int query(int x, int y){ ?int L = 0, R = ncnt; ?while(L < R) ???{ ?????int mid = (L + R + 1) >> 1; ?????if(judge(x, y, mid)) L = mid; ?????else R = mid - 1; ???} ?return L;}int main(){ ?p[0] = 1; for(int i = 1; i < maxn; ++i) p[i] = p[i - 1] * 47; //学姐强啊 ?scanf("%s", s + 2); ncnt = strlen(s + 2) + 2; ?s[1] = s[ncnt] = ‘f‘; ?build(1, ncnt, 0); ?for(int i = 1; i <= ncnt && !root; ++i) if(!t[i].fa) root = i; ?m = read(); ?for(int i = 1, x; i <= m; ++i) ???{ ?????scanf("%s", c); x = read() + 1; ?????if(c[0] == ‘Q‘) ???{ ?????int y = read() + 1; ?????write(query(x, y)), enter; ???} ?????else ???{ ?????scanf("%s", tp); ?????if(c[0] == ‘R‘) update(x); ?????else insert(x); ???} ?????//_PrintTr(root); ???} ?return 0;}[JSOI2008]火星人
原文地址：https://www.cnblogs.com/mrclr/p/10064433.html