Description
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，
我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，
火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串
，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，
如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说
，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此
复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。
Input
第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操
作有3种，如下所示
1、询问。语法：Qxy，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。
2、修改。语法：Rxd，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字
符串长度。
3、插入：语法：Ixd，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字
符串开头插入。限制：x不超过当前字符串长度
题解：splay维护区间hash值，每次查询对答案二分，然后O（1）判断相不相等，注意考虑split时l，r为边界的情况
View Code
/************************************************************** Problem: 1014 User: walfy Language: C++ Result: Accepted Time:6708 ms Memory:7424 kb ****************************************************************/ //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector<int> #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pli pair<ll,int> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-11; const int N=100000+10,maxn=5000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; const ull bs=151; char a[N]; ull p[N]; struct Splay{ struct Node{ Node *ch[2]; int v,s;ull ha; int cmp(int x)const{ int d = x - ch[0]->s; if(d==1)return -1; return d<=0?0:1; } }; inline void maintain(Node *o) { o->s = 1 + o->ch[0]->s+o->ch[1]->s; o->ha = o->v; if(o->ch[1]!=null) { o->ha=o->ha+o->ch[1]->ha*bs; } if(o->ch[0]!=null) { o->ha=o->ha*p[o->ch[0]->s]+o->ch[0]->ha; } } Node *null; inline void Rotate(Node* &o,int d) { Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; maintain(o);maintain(k); o = k; } inline void splay(Node* &o,int k) { int d = o->cmp(k); if(d==1)k-=o->ch[0]->s+1; if(d!=-1) { Node* p=o->ch[d]; int d2=p->cmp(k); int k2=(d2==0?k:k-p->ch[0]->s-1); if(d2!=-1) { splay(p->ch[d2],k2); if(d==d2)Rotate(o,d^1); else Rotate(o->ch[d],d); } Rotate(o,d^1); } } inline Node* Merge(Node* left,Node* right) { splay(left,left->s); left->ch[1]=right; maintain(left); return left; } inline void split(Node* o,int k,Node* &left,Node* &right) { splay(o,k); right = o->ch[1]; o->ch[1]=null; left=o; maintain(left); } Node *root,*left,*right; inline void init(int sz) { null = new Node; null->s=0; root = new Node; root->v=(int)a[1]-'a';root->s=1; root->ch[0]=root->ch[1]=null; maintain(root); Node* p; for(int i=2;i<=sz;i++) { p = new Node; p->v=a[i]-'a';p->s=0; p->ch[0]=root;p->ch[1]=null; root=p; maintain(root); } // debug(root); } inline void ins() { int x;char c[5]; scanf("%d%s",&x,c); Node* p=new Node; p->v=(int)(c[0]-'a');p->s=1; p->ch[0]=p->ch[1]=null; if(x==0) { root=Merge(p,root); } else { split(root,x,left,right); root=Merge(Merge(left,p),right); } } inline ull getans(int l,int r) { ull ans=0; if(l==1&&r==root->s)ans=root->ha; else if(l==1) { split(root,r,left,right); ans=left->ha; root=Merge(left,right); } else if(r==root->s) { split(root,l-1,left,right); ans=right->ha; //printf("%lld ",right->ha); root=Merge(left,right); } else { split(root,r,left,right); Node *tel,*ter; split(left,l-1,tel,ter); ans=ter->ha; root=Merge(Merge(tel,ter),right); } //printf("%d %d %lld ",l,r,ans); return ans; } inline void query() { int x,y;scanf("%d%d",&x,&y); if(x>y)swap(x,y); int n=root->s; int l=0,r=n-y+2; while(l<r-1) { //printf("%d %d %lld %d %d %lld ",x,x+m-1,getans(x,x+m-1),y,y+m-1,getans(y,y+m-1)); int m=(l+r)>>1; ull te1=getans(x,x+m-1),te2=getans(y,y+m-1); if(te1==te2)l=m; else r=m; } printf("%d ",l); } inline void debug(Node* o) { if(o->ch[0]!=null)debug(o->ch[0]); printf("%d %lld %d ",o->v,o->ha,o->s); if(o->ch[1]!=null)debug(o->ch[1]); } }sp; int main() { p[0]=1; for(int i=1;i<N;i++)p[i]=p[i-1]*bs; scanf("%s",a+1); int len=strlen(a+1); // for(int i=1;i<=len;i++)printf("%d ",a[i]-'a');puts(""); sp.init(len); int m;scanf("%d",&m); while(m--) { char op[5]; scanf("%s",op); if(op[0]=='Q')sp.query(); else if(op[0]=='R') { int x;char c[5]; scanf("%d%s",&x,c); sp.split(sp.root,x,sp.left,sp.right); sp.left->v=(int)c[0]-'a'; sp.root=sp.Merge(sp.left,sp.right); } else sp.ins(); } return 0; } /*********************** 998244353 ***********************/