题目:
题解:
#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[10]; void upt(int u) { sz[u]=sz[ls[u]]+sz[rs[u]]+1; hsh[u]=hsh[ls[u]]+val[u]*pw[sz[ls[u]]]+hsh[rs[u]]*pw[sz[ls[u]]+1]; } 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 0; int u=++idx,mid=l+r>>1; val[u]=s[mid]-'a'+1,fa[u]=pre; ls[u]=build(l,mid-1,u); rs[u]=build(mid+1,r,u); upt(u); return u; } int find(int x) { int u=root; while(sz[ls[u]]!=x) if (x<=sz[ls[u]]-1) u=ls[u]; else x-=sz[ls[u]]+1,u=rs[u]; return u; } void insert(int pos,int x) { int u=find(pos),v=find(pos+1); splay(u,0),splay(v,u); ls[v]=++idx,fa[idx]=v,val[idx]=x,sz[idx]=1; splay(idx,0); } void change(int pos,int x) { int u=find(pos); val[u]=x; splay(u,0); } ll gethsh(int pos,int len) { int u=find(pos-1),v=find(pos+len); splay(u,0),splay(v,u); return hsh[ls[v]]; } int query(int a,int b) { int l=0,r=sz[root]-max(a,b)-1,mid; while (l<r) { mid=l+r+1>>1; if (gethsh(a,mid)==gethsh(b,mid)) l=mid; else r=mid-1; } return l; } int main() { scanf("%s",s+1); n=strlen(s+1); pw[0]=1; for (int i=1;i<N;i++) pw[i]=pw[i-1]*Base; root=build(0,n+1,0); scanf("%d",&m); while (m--) { scanf("%s",op); if (op[0]=='Q') { scanf("%d%d",&a,&b); printf("%d ",query(a,b)); } else if (op[0]=='I') { int pos; scanf("%d%s",&pos,op); insert(pos,op[0]-'a'+1); } else if (op[0]=='R') { int pos; scanf("%d%s",&pos,op); change(pos,op[0]-'a'+1); } } return 0; }