题目:
题解:
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
#define N 100010
#define Base 29
#define which(x) (ls[fa[(x)]]==(x))
using namespace std;
int n,m,idx,root,fa[N],ls[N],rs[N],val[N],sz[N],a,b;
ll hsh[N],pw[N];
char s[N],op[];
void upt(int u)
{
sz[u]=sz[ls[u]]+sz[rs[u]]+;
hsh[u]=hsh[ls[u]]+val[u]*pw[sz[ls[u]]]+hsh[rs[u]]*pw[sz[ls[u]]+];
}
void rotate(int u)
{
int v=fa[u],w=fa[v],b=which(u)?rs[u]:ls[u];
if (w) which(v)?ls[w]=u:rs[w]=u;
which(u)?(ls[v]=b,rs[u]=v):(rs[v]=b,ls[u]=v);
fa[u]=w,fa[v]=u;
if (b) fa[b]=v;
upt(v),upt(u);
}
void splay(int u,int tar)
{
while (fa[u]!=tar)
{
if (fa[fa[u]]!=tar)
(which(u)==which(fa[u]))?rotate(fa[u]):rotate(u);
rotate(u);
}
if (!tar) root=u;
}
int build(int l,int r,int pre)
{
if (l>r) return ;
int u=++idx,mid=l+r>>;
val[u]=s[mid]-'a'+,fa[u]=pre;
ls[u]=build(l,mid-,u);
rs[u]=build(mid+,r,u);
upt(u);
return u;
}
int find(int x)
{
int u=root;
while(sz[ls[u]]!=x)
if (x<=sz[ls[u]]-) u=ls[u];
else x-=sz[ls[u]]+,u=rs[u];
return u;
}
void insert(int pos,int x)
{
int u=find(pos),v=find(pos+);
splay(u,),splay(v,u);
ls[v]=++idx,fa[idx]=v,val[idx]=x,sz[idx]=;
splay(idx,);
}
void change(int pos,int x)
{
int u=find(pos);
val[u]=x;
splay(u,);
}
ll gethsh(int pos,int len)
{
int u=find(pos-),v=find(pos+len);
splay(u,),splay(v,u);
return hsh[ls[v]];
}
int query(int a,int b)
{
int l=,r=sz[root]-max(a,b)-,mid;
while (l<r)
{
mid=l+r+>>;
if (gethsh(a,mid)==gethsh(b,mid)) l=mid;
else r=mid-;
}
return l;
}
int main()
{
scanf("%s",s+);
n=strlen(s+);
pw[]=;
for (int i=;i<N;i++)
pw[i]=pw[i-]*Base;
root=build(,n+,);
scanf("%d",&m);
while (m--)
{
scanf("%s",op);
if (op[]=='Q')
{
scanf("%d%d",&a,&b);
printf("%d\n",query(a,b));
}
else if (op[]=='I')
{
int pos;
scanf("%d%s",&pos,op);
insert(pos,op[]-'a'+);
}
else if (op[]=='R')
{
int pos;
scanf("%d%s",&pos,op);
change(pos,op[]-'a'+);
}
}
return ;
}