感觉很少有人这一题 70 分啊 。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
inline bool id(const char ch) {
	return ch>='0'&&ch<='9';
}
inline int read(void) {
	int s=0,f=0;
	char ch=getchar();
	while(!id(ch)) f=(ch=='-'),ch=getchar();
	while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return f?-s:s;
}
const int MAXN=100000+10;
int n,root,idx,_pow[MAXN];
string k;
struct Node {
	int l,r,sze,hsh,val,chr;
}tr[MAXN];
mt19937 myrand(time(NULL));
inline int get_node(const int chr) {
	return tr[++idx]=Node{0,0,1,chr,myrand(),chr},idx;	
}
inline void push_up(const int u) {
	tr[u].sze=tr[tr[u].l].sze+tr[tr[u].r].sze+1,tr[u].hsh=tr[tr[u].r].hsh+_pow[tr[tr[u].r].sze]*tr[u].chr+_pow[tr[tr[u].r].sze+1]*tr[tr[u].l].hsh;
	return ;
}
void split(const int u,const int k,int &x,int &y) {
	if(!u) return x=y=0,void();
	if(k<=tr[tr[u].l].sze) y=u,split(tr[u].l,k,x,tr[u].l);
	else x=u,split(tr[u].r,k-tr[tr[u].l].sze-1,tr[u].r,y);
	push_up(u);
	return;
}
int merge(const int x,const int y) {
	if(!x||!y) return x|y;
	if(tr[x].val>=tr[y].val) return tr[x].r=merge(tr[x].r,y),push_up(x),x;
	return tr[y].l=merge(x,tr[y].l),push_up(y),y;
}
void update(const int x,const int u,const int chr) {
	if(x==tr[tr[u].l].sze+1) tr[u].chr=chr;
	else if(x<=tr[tr[u].l].sze) update(x,tr[u].l,chr);
	else update(x-tr[tr[u].l].sze-1,tr[u].r,chr);
	push_up(u);
	return;
}
inline void init(void) {
	for(int i=0;i<k.size();i++) {
		int chr=k[i]-'a';
		root=merge(root,get_node(chr));	
	}
	return;
}
inline int HASH(const int u,const int v) {
	int A,B,C,D;
	split(root,u-1,A,B),split(B,v-u+1,C,D);	
	int ans=tr[C].hsh;
	root=merge(merge(A,C),D);
	return ans;
//	cout<<"WULA!"<<u<<' '<<v<<'\n';
}
signed main() {
	_pow[0]=1;
	for(int i=1;i<=100000;i++) _pow[i]=_pow[i-1]*26;
	cin>>k;
	init();
	n=read();
	for(int i=1;i<=n;i++) {
		char ch=getchar();
		while(!(ch>='A'&&ch<='Z')) ch=getchar();	
		if(ch=='Q') {
			int x=read(),y=read();
			if(x>y) swap(x,y);
			int u=x,v=y;
			for(signed long long j=20;j>=0;j--) if(v+(1<<j)-1<=tr[root].sze&&HASH(u,u+(1<<j)-1)==HASH(v,v+(1<<j)-1)) u+=(1<<j),v+=(1<<j);
			printf("%lld\n",v-y);
		}
		if(ch=='R') {
			int x=read();
			char ch=getchar();
			while(!(ch>='a'&&ch<='z')) ch=getchar();
			update(x,root,ch-'a');
		}
		if(ch=='I') {
			int x=read(),A,B;
			char ch=getchar();
			while(!(ch>='a'&&ch<='z')) ch=getchar();
			split(root,x,A,B),root=merge(merge(A,get_node(ch-'a')),B);	
		}
	}
	return 0;
}