Splay维护hash，查询二分
$a[x].vl=a[lc].vl*ha[a[rc].sz+1]+a[x].w*ha[a[rc].sz]+a[rc].vl$
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
int read(){
char c=getchar(); int x=;
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') x=x*+c-,c=getchar();
return x;
}
#define N 300005
const int bas=;
int n,Q; char q[N],q1[]; ull ha[N];
struct node{int ch[],sz,fa; ull vl,w;}a[N];
struct Splay{
#define lc a[x].ch[0]
#define rc a[x].ch[1]
#define mid (l+r)/2
int rt,u;
inline void up(int x){
a[x].sz=a[lc].sz+a[rc].sz+,
a[x].vl=a[lc].vl*ha[a[rc].sz+]+a[x].w*ha[a[rc].sz]+a[rc].vl;
}
inline int whi(int y,int x){return a[y].ch[]==x;}
void turn(int x,int &k){
int y=a[x].fa,z=a[y].fa,l=whi(y,x),r=l^;
if(y==k) k=x;
else a[z].ch[whi(z,y)]=x;
a[a[x].ch[r]].fa=y; a[y].fa=x; a[x].fa=z;
a[y].ch[l]=a[x].ch[r]; a[x].ch[r]=y;
up(y); up(x);
}
void splay(int x,int &k){
for(;x!=k;turn(x,k)){
int y=a[x].fa,z=a[y].fa;
if(y!=k) turn(whi(z,y)==whi(y,x)?y:x,k);
}
}
int kth(int k){
int x=rt;
while(a[lc].sz+!=k){
if(a[lc].sz>=k) x=lc;
else k=k-a[lc].sz-,x=rc;
}return x;
}
inline void rep(int x,ull k){a[x=kth(x)].w=k,splay(x,rt);}
void ins(int x,ull k){
x=kth(x); ++u;
if(!rc) rc=u;
else{for(x=rc;lc;x=lc); lc=u;}
a[u].fa=x; a[u].w=k; up(u); splay(u,rt);
}
ull Fi(int x,int y){
int L=kth(x-),R=kth(y+);
splay(L,rt); splay(R,a[L].ch[]);
return a[a[R].ch[]].vl;
}
int ask(int x,int y){
if(x>y) swap(x,y);
int l=,r=u-y,re=;
while(l<=r){
if(Fi(x,x+mid-)!=Fi(y,y+mid-)) r=mid-;
else re=mid,l=mid+;
}return re;
}
int build(int Fa,int l,int r){
a[mid].w=(ull)q[mid-]; a[mid].fa=Fa; ++u;
if(l<mid) a[mid].ch[]=build(mid,l,mid-);
if(r>mid) a[mid].ch[]=build(mid,mid+,r);
up(mid); return mid;
}
}S;
int main(){
scanf("%s",q+); n=strlen(q+); ha[]=;
for(int i=;i<N;++i) ha[i]=ha[i-]*bas;
S.rt=S.build(,,n+); Q=read();//建树时记得加入边界
for(int i=,w1,w2;i<=Q;++i){
scanf("%s",q1);
if(q1[]=='Q') w1=read(),w2=read(),printf("%d\n",S.ask(w1+,w2+));
if(q1[]=='R') w1=read(),scanf("%s",q1),S.rep(w1+,(ull)q1[]);
if(q1[]=='I') w1=read(),scanf("%s",q1),S.ins(w1+,(ull)q1[]);
}return ;
}