#1，#5，#6，#7，#8 莫名 $\rm MLE$，求助

做法：无旋 $\rm treap$ + $\rm hash$ + 倍增

#include <cstdio>
#include <cstdlib>
#include <ctime> 
#include <cstring>
#include <algorithm>
using namespace std;
int read(){
	char ch=getchar();int num=0;
	while(ch<'0'||'9'<ch) ch=getchar();
	while('0'<=ch&&ch<='9') {num=num*10+ch-'0'; ch=getchar();}
	return num;
}
const int MAXN=1e5+2;
char s[MAXN];
int N,M;
unsigned long long val[MAXN],pw[MAXN];
int ch[MAXN],ls[MAXN],rs[MAXN],pri[MAXN],sze[MAXN];
int Rt,tot;
void upd(int x){
	sze[x]=sze[ls[x]]+1+sze[rs[x]];
	val[x]=val[ls[x]] + (unsigned long long)ch[x]*pw[sze[ls[x]]] + val[rs[x]]*pw[sze[ls[x]]+1];
}
void buildTree(int L,int R,int &x){
	if(L>R)return;
	int mid=(L+R)>>1;
	x=++tot; ch[x]=s[mid]-'a'+1; pri[x]=rand();
	if(L==R){ sze[x]=1;val[x]=ch[x]; return; }
	buildTree(L,mid-1,ls[x]);
	buildTree(mid+1,R,rs[x]);
	upd(x);
}
void split(int x,int &a,int &b,int k){
	if(!x){ a=b=0;return; }
	if(k<=sze[ls[x]]) b=x,split(ls[x],a,ls[b],k);
	else a=x,split(rs[x],rs[a],b,k-sze[ls[x]]-1);
	upd(x);
}
int merge(int a,int b){
	if(!a||!b) return a+b;
	if(pri[a]<pri[b]) {rs[a]=merge(rs[a],b),upd(a);return a;}
	else {ls[b]=merge(a,ls[b]);upd(b);return b;} 
}
unsigned long long query(int l,int r){
	int a,b,c; unsigned long long ret;
	split(Rt,a,c,r); split(a,a,b,l-1);
	ret=val[b];
	Rt=merge(merge(a,b),c);
	return ret;
}
int newnode(char x){
	int d=++tot;
	ch[d]=val[d]=x-'a'+1; pri[d]=rand(); sze[d]=1;
	return d;
}
int main(){
	srand(time(0));
	scanf("%s",s+1);N=strlen(s+1);
	pw[0]=1; for(int i=1;i<=MAXN-2;i++) pw[i]=pw[i-1]*27;
	buildTree(1,N,Rt);
	M=read();
	char opt,d;
	int x,y,a,b,c;
	unsigned long long val1,val2;
	for(int i=1;i<=M;i++){
		scanf("\n%c",&opt);
		if(opt=='Q'){
			x=read();y=read(); if(x>y) swap(x,y);
			int nowx=x,nowy=y;//目前 [x,nowx) & [y,nowy) 匹配 
			for(int j=18;j>=0;j--){
				if((1<<j)>N-nowy+1) continue;
				val1=query(x,nowx+(1<<j)-1);
				val2=query(y,nowy+(1<<j)-1);
			//	printf("[%d,%d) & [%d,%d) : chk=%d\n",x,nowx+(1<<j),y,nowy+(1<<j),val1==val2);
				if(val1==val2) nowx+=(1<<j),nowy+=(1<<j);
			}
			printf("%d\n",nowx-x);
		}else if(opt=='R'){
			x=read();scanf("%c",&d);
			split(Rt,a,b,x-1); split(Rt,b,c,1);
			Rt=merge(merge(a,newnode(d)),c);
		}else if(opt=='I'){
			x=read();scanf("%c",&d);
			split(Rt,a,b,x); ++N;
			Rt=merge(merge(a,newnode(d)),b); 
		}
	}
	return 0;
}