题意不赘述了，太清晰了。
说题解：首先依据原字符串建立SPT。首尾建议多加一个空白字符。
给一个树构图，依照平衡树的前后大小顺序性质能够使它们始终维持为一个序列，而且能够通过rank找到序列的第k个。
树构造完了以后。点插入，点改动，询问神马的代码里都有具体凝视。
/*
BZOJ 1014
新手看的时候建议从main函数处開始，依照执行顺序来脑模拟。 P.S. 这个代码的hash用的是自然溢出而非取mod运算。
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 250010
#define is(x) (son[fa[x]][1]==x)
using namespace std;
typedef unsigned long long LL;
char start[N];
int digit[N];
LL power[N]={1};
struct node
{
int root,n;
LL hash[N];
int val[N],fa[N],son[N][2],size[N];
inline void update(int p)
{
size[p]=size[son[p][0]]+size[son[p][1]]+1;
hash[p]=hash[son[p][0]]*power[size[son[p][1]]+1]+val[p]*power[size[son[p][1]]]+hash[son[p][1]];
/*此代码是得到53位制的hash值，hash[p]表示该段的hash值。想一下就非常好理解。*/
}
inline void Build(int l,int r,int mid)
{
if(l<mid)/*左边有数*/
{
int lmid=l+mid-1>>1;
Build(l,mid-1,lmid);
fa[lmid]=mid;
son[mid][0]=lmid;
}
if(mid<r)/*右边有数*/
{
int rmid=mid+1+r>>1;
Build(mid+1,r,rmid);
fa[rmid]=mid;
son[mid][1]=rmid;
}
val[mid]=digit[mid],update(mid);
/*val表示当前字符（数字版）*/
}
inline void link(int x,int y,int d){son[y][d]=x;fa[x]=y;}
inline void Rotate(int x)
{
int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
if(t)fa[t]=y;son[y][id]=t;
link(x,z,is(y));
link(y,x,!id);
update(y);
}
inline void Splay(int x,int k)
{
int y,z;
while(fa[x]!=k)
{
y=fa[x];
z=fa[y];
if(z==k){Rotate(x);break;}
if(is(x)==is(y))Rotate(y),Rotate(x);
else Rotate(x),Rotate(x);
}
update(x);
if(!k)root=x;
}
inline int Select(int rank,int k)/*找到该节点并将它旋转到k的儿子处（k=0则旋到根）*/
{
if(size[root]<rank)return -1;/*找不到*/
int x=root;
while(size[son[x][0]]+1!=rank)/*循环条件：根不是要找的节点*/
{
if(size[son[x][0]]+1>rank)x=son[x][0];
else rank=rank-size[son[x][0]]-1,x=son[x][1];
}/*已经找到要找的节点*/
Splay(x,k);
return x;
}
inline void newnode(int &x,int y,int w)
{
x=++n;
son[x][0]=son[x][1]=0;
val[x]=w;
fa[x]=y;
size[x]=1;
}
inline void Insert(int x,int p)
{
int l=Select(x,0),r=Select(x+1,l);
/*x到根。x+1到根的右子节点。即保证r的左子树为NULL*/
newnode(son[r][0],r,p);
Splay(n,0);
}
inline void Change(int x,int p){x=Select(x,0),val[x]=p,Splay(x,0);}
inline bool check(int a,int b,int len)
{
int x;
Select(a-1,0);x=Select(a+len,root);
/*把区间(此处为a開始的len个)rotate到lrt*/
if(x==-1)return 0;
LL hash1=hash[son[x][0]];
Select(b-1,0);x=Select(b+len,root);
if(x==-1)return 0;
LL hash2=hash[son[x][0]];
return hash1==hash2;
}
}tree;
void handle()
{
int i,m,l,r,mid,L,R;
char a[5];
for(int i=1;i<N;i++)power[i]=power[i-1]*53;
scanf("%s",start);
tree.n=strlen(start)+2;/*左右各添一个空白字符*/
for(int i=2;i<=tree.n-1;i++)digit[i]=start[i-2]-'a'+1;
tree.root=(1+tree.n)>>1,tree.Build(1,tree.n,1+tree.n>>1);/*建树*/
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",a);
/*以下l+1的缘故是由于序列左右各添了一个空白字符*/
if(a[0]=='Q')
{
scanf("%d %d",&L,&R);
l=0,r=tree.n;
while(l<r)
{/*二分出解*/
mid=l+r>>1;
if(tree.check(L+1,R+1,mid))l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
}
else if(a[0]=='R')
{
scanf("%d %s",&l,a);
tree.Change(l+1,a[0]-'a'+1);
}
else
{
scanf("%d %s",&l,a);
tree.Insert(l+1,a[0]-'a'+1);
}
}
}
int main()
{
// freopen("test.in","r",stdin);
handle();
return 0;
}