Description
我们定义LCQ(x,y)为x这个后缀和y这个后缀的LCP(最长公共前缀)
给出一个字符串，可以在中间插入某一个字符，或者修改某一个字符，并且维护LCQ.
Q<=1.5*10^5，|S|<=10^5，字符集为所有的小写字母，询问数<=10^4.
Solution
一眼看到还以为是裸SA（智商堪忧）
后来发现有动态插入，立马想到splay。
维护什么呢？Hash值！
然后每次询问二分答案判定是否合法。
打一个splay需要20min，但用splayA一题可能需要2h+
这道题常数写大了，一直TLE
然后一怒之下把LL扔掉了，然后就。。。
踩线过啦！（各位4ms的爷请收下我的膝盖Orz）
所以，当你看到你跑多了100ms的话，LL神教向你招手。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 100010
using namespace std;
typedef long long ll;
const int mo=;
int f[N],t[N][],size[N],h[N],mi[N],key[N],tot,n,m,x,y,root;
char s[N],ch[];
void updata(int x) {
int l=t[x][],r=t[x][];
size[x]=size[l]+size[r]+;
h[x]=h[l]+(ll)key[x]*mi[size[l]]%mo+(ll)h[r]*mi[size[l]+]%mo;
h[x]%=mo;
}
int build(int l,int r,int fa) {
if (l>r) return ;
int m=(l+r)/;
f[m]=fa;size[m]=;
h[m]=key[m]=s[m]-'a';
if (l==r) return m;
t[m][]=build(l,m-,m);
t[m][]=build(m+,r,m);
updata(m);return m;
}
int son(int x) {
if (t[f[x]][]==x) return ;else return ;
}
void rotate(int x) {
int y=f[x],z=son(x);f[x]=f[y];
if (f[x]) t[f[x]][son(y)]=x;
if (t[x][-z]) f[t[x][-z]]=y;
t[y][z]=t[x][-z];t[x][-z]=y;f[y]=x;
updata(y);updata(x);
}
void splay(int x,int y) {
while (f[x]!=y) {
if (f[f[x]]!=y)
if (son(x)==son(f[x])) rotate(f[x]);
else rotate(x);
rotate(x);
}
if (!y) root=x;
}
int find(int x,int id) {
if (!x) return ;
int l=t[x][],r=t[x][];
if (size[l]+==id) return x;
if (size[l]+>id) return find(l,id);
else return find(r,id-size[l]-);
}
void insert(int x,int c) {
int y=find(root,x);splay(y,);
int z=find(root,x+);splay(z,y);
t[z][]=++tot;f[tot]=z;key[tot]=h[tot]=c;size[tot]=;
updata(z);updata(y);
}
void change(int x,int c) {
int y=find(root,x);splay(y,);
key[y]=c;updata(y);
}
int query(int l,int r) {
int x=find(root,l-);splay(x,);
int y=find(root,r+);splay(y,x);
return h[t[y][]];
}
int main() {
scanf("%s",s+);int n=strlen(s+);
mi[]=;fo(i,,N-) mi[i]=mi[i-]*%mo;
root=build(,n+,);tot=n+;
for(scanf("%d",&m);m;m--) {
scanf("%s",s);
if (s[]=='Q') {
scanf("%d%d",&x,&y);
int l=,r=min(tot-x,tot-y);x++;y++;
while (l<r) {
int mid=(l+r)/;
if (query(x,x+mid-)==query(y,y+mid-)) l=mid+;
else r=mid;
}
printf("%d\n",l-);
} else if (s[]=='R') {
scanf("%d%s",&x,ch);
change(++x,ch[]-'a');
} else {
scanf("%d%s",&x,ch);
insert(++x,ch[]-'a');
}
}
}