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不超过当前字符串长度
Output
对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
Sample Input
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11
Sample Output
1
0
2
1
HINT
1、所有字符串自始至终都只有小写字母构成。
2、M<=150,000
3、字符串长度L自始至终都满足L<=100,000
4、询问操作的个数不超过10,000个。
对于第1，2个数据，字符串长度自始至终都不超过1,000
对于第3，4，5个数据，没有插入操作。
首先将字符串变为一棵ｓｐｌａｙ，然后对于每个点计算出它的子树的ｈａｓｈ值，x[k].z=(x[x[k].s[0]].z*cf[x[x[k].s[1]].zs+1]%p+x[k].c*cf[x[x[k].s[1]].zs]%p+x[x[k].s[1]].z)％p;
cf[i]表示质数的ｉ次方。插入与修改操作与普通ｓｐｌａｙ无差别。而对于询问二分答案，进行区间查找即可，看哈希值是否相同。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef unsigned long long ll; const int N=100005; const ll p=9999991; struct X { int fa,s[2],zs,c; ll z; }x[N]; char c[N]; int ge=1; ll cf[N]; void pu(int k) { x[k].zs=x[x[k].s[0]].zs+1+x[x[k].s[1]].zs; x[k].z=(x[x[k].s[0]].z*cf[x[x[k].s[1]].zs+1]%p+x[k].c*cf[x[x[k].s[1]].zs]%p+x[x[k].s[1]].z)%p; } void chan(int k,int a,char zf) { if(x[x[k].s[0]].zs>=a) chan(x[k].s[0],a,zf); else if(x[x[k].s[0]].zs+1==a) x[k].c=zf; else chan(x[k].s[1],a-x[x[k].s[0]].zs-1,zf); pu(k); } void xz(int a,int &k) { int b=x[a].fa,bb=x[b].s[1]==a,cc=x[x[b].fa].s[1]==b; if(k==b) k=a; else x[x[b].fa].s[cc]=a; x[a].fa=x[b].fa; x[x[b].s[bb]=x[a].s[!bb]].fa=b; x[x[a].s[!bb]=b].fa=a; pu(b); } void splay(int& k,int a) { while(k!=a) { int b=x[a].fa; if(b!=k) if(x[b].s[1]==a^x[x[b].fa].s[1]==b) xz(a,k); else xz(b,k); xz(a,k); } pu(a); } int find(int k,int a) { if(x[x[k].s[0]].zs>=a) return find(x[k].s[0],a); else if(x[x[k].s[0]].zs+1==a) return k; return find(x[k].s[1],a-x[x[k].s[0]].zs-1); } ll ask(int l,int r) { splay(ge,find(ge,l)); splay(x[ge].s[1],find(ge,r)); return x[x[x[ge].s[1]].s[0]].z; } int main() { freopen("a.in","r",stdin),freopen("a.out","w",stdout); scanf("%s",c); int l=strlen(c),sl=l+2; x[l+2].fa=l+1; x[l+2].z=x[l+2].c=0; x[l+2].zs=cf[0]=1; for(int i=1;i<N;++i) cf[i]=cf[i-1]*9999973%p; for(int i=l-1;i>=0;--i) { x[i+2].fa=i+1; x[i+2].zs=l-i+1; x[i+2].s[1]=i+3; x[i+2].c=c[i]; x[i+2].z=(x[i+3].z+c[i]*cf[l-i])%p; } x[1].c=0; x[1].z=x[2].z; x[1].zs=l+2; x[1].s[1]=2; scanf("%d",&l); while(l--) { char zf; scanf(" %c",&zf); if(zf=='Q') { int a,b,l=0,r; scanf("%d%d",&a,&b); ++a;++b; r=min(sl-a,sl-b)+1; while(l<r-1) { int mid=(l+r)>>1; if(ask(a-1,a+mid)==ask(b-1,b+mid)) l=mid; else r=mid; } printf("%d ",l); } else if(zf=='R') { int a; scanf("%d %c",&a,&zf); chan(ge,a+1,zf); } else { int a; scanf("%d %c",&a,&zf); splay(ge,find(ge,a+1)); splay(x[ge].s[1],find(ge,a+2)); x[x[ge].s[1]].s[0]=++sl; x[sl].z=x[sl].c=zf; x[sl].fa=x[ge].s[1]; x[sl].zs=1; pu(x[ge].s[1]); pu(ge); } } return 0; }