平衡树维护哈希值就完了
写烂要被卡
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
mt19937 rnd(time(NULL));
#define uint unsigned int
const int N=100005;
uint bas=233,p[N];
namespace FHQ_Treap{
int siz[N],lc[N],rc[N],tot,rt;
uint a[N],val[N];
inline int newnode(int k){
int u=++tot;siz[u]=1,val[u]=a[u]=k;
return u;
}
inline void pushup(int u){
siz[u]=siz[lc[u]]+siz[rc[u]]+1;
val[u]=val[lc[u]]+val[rc[u]]*p[siz[lc[u]]+1]+a[u]*p[siz[lc[u]]];
}
inline void split(int u,int &r1,int &r2,int k){
if(!u){r1=r2=0;return;}
if(siz[lc[u]]>=k)
r2=u,split(lc[u],r1,lc[r2],k);
else
r1=u,split(rc[u],rc[r1],r2,k-siz[lc[u]]-1);
pushup(u);
}
inline void merge(int &u,int r1,int r2){
if(!r1||!r2){u=r1+r2;return;}
if((unsigned)rnd()%(siz[r1]+siz[r2])<siz[r1])
u=r1,merge(rc[u],rc[r1],r2);
else u=r2,merge(lc[u],r1,lc[r2]);
pushup(u);
}
inline void insert(int p,int k){
int r1=0,r2=0,u=newnode(k);
split(rt,r1,r2,p);
merge(r1,r1,u);
merge(rt,r1,r2);
}
inline void update(int k,int v){
int r1=0,r2=0,r3=0;
split(rt,r1,r2,k-1);
split(r2,r2,r3,1);
a[r2]=val[r2]=v;
merge(r1,r1,r2);
merge(rt,r1,r3);
}
inline uint query(int u,int k){
int r1=0,r2=0,r3=0;
split(rt,r1,r2,u-1);
split(r2,r2,r3,k);
uint res=val[r2];
merge(r2,r2,r3);
merge(rt,r1,r2);
return res;
}
}
using namespace FHQ_Treap;
int n;
char op[4],s[N];
inline int ask(int x,int y){
int l=1,r=siz[rt]-max(x,y)+1,res=0;
while(l<=r){
int mid=(l+r)>>1;
if(query(x,mid)==query(y,mid))l=mid+1,res=mid;
else r=mid-1;
}return res;
}
signed main(){
srand(time(NULL));
p[0]=1,scanf("%s",s+1);
for(int i=1;i<N;i++)p[i]=p[i-1]*bas;
for(int i=1,l=strlen(s+1);i<=l;i++)insert(i-1,s[i]-'a'+1);
n=read();
for(int i=1;i<=n;i++){
scanf("%s",op+1);
if(op[1]=='Q'){
int x=read(),y=read();
cout<<ask(x,y)<<'
';
}
else if(op[1]=='R'){
int x=read();scanf("%s",s+1);
update(x,s[1]-'a'+1);
}
else {
int x=read();scanf("%s",s+1);
insert(x,s[1]-'a'+1);
}
}
}