[JSOI2008]火星人

嘟嘟嘟

嗯。

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 register typedef 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; }

转载于:https://www.cnblogs.com/mrclr/p/10064433.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/98799225

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。