火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，
我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，
火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串
，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，
如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说
，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此
复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。

　　第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操
作有3种，如下所示
1、询问。语法：Qxy，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。
2、修改。语法：Rxd，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字
符串长度。
3、插入：语法：Ixd，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字
符串开头插入。限制：x不超过当前字符串长度

　　对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

5
1
0
2
1

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define lll tr[spc].ch[0]

 #define rrr tr[spc].ch[1]

 #define ls ch[0]

 #define rs ch[1]

 typedef unsigned long long lnt;

 const int N=;

 const lnt M=9827601ull;

 struct trnt{

     int ch[];

     int fa;

     int wgt;

     lnt val;

     lnt hax;

 }tr[N];

 int n,m;

 int root;

 int siz;

 lnt mal[N];

 char lne[N];

 char cmd[];

 lnt a[N];

 bool whc(int spc)

 {

     return tr[tr[spc].fa].rs==spc;

 }

 void pushup(int spc)

 {

     tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+;

     tr[spc].hax=tr[lll].hax*mal[tr[rrr].wgt+]+tr[spc].val*mal[tr[rrr].wgt]+tr[rrr].hax;

     return ;

 }

 int place(int spc,int rnk)

 {

     if(tr[lll].wgt>=rnk)

         return place(lll,rnk);

     if(tr[lll].wgt+==rnk)

         return spc;

     return place(rrr,rnk-tr[lll].wgt-);

 }

 void rotate(int spc)

 {

     int f=tr[spc].fa;

     bool k=whc(spc);

     tr[f].ch[k]=tr[spc].ch[!k];

     tr[spc].ch[!k]=f;

     tr[tr[f].fa].ch[whc(f)]=spc;

     tr[spc].fa=tr[f].fa;

     tr[f].fa=spc;

     tr[tr[f].ch[k]].fa=f;

     pushup(f);

     pushup(spc);

     return ;

 }

 void splay(int spc,int f)

 {

     while(tr[spc].fa!=f)

     {

         int ft=tr[spc].fa;

         if(tr[ft].fa==f)

         {

             rotate(spc);

             break;

         }

         if(whc(spc)^whc(ft))

             rotate(spc);

         else

             rotate(ft);

         rotate(spc);

     }

     if(!f)

         root=spc;

 }

 void build(int l,int r,int &spc,int f)

 {

     if(l>r)

         return ;

     spc=++siz;

     int mid=(l+r)>>;

     tr[spc].fa=f;

     tr[spc].val=a[mid];

     build(l,mid-,lll,spc);

     build(mid+,r,rrr,spc);

     pushup(spc);

     return ;

 }

 bool LCQ(int la,int lb,int len)

 {

     if(la+len->n||lb+len->n)

         return false;

     splay(place(root,la),);

     splay(place(root,la+len+),root);

     int spc=tr[tr[root].rs].ls;

     lnt a1=tr[spc].hax;

     splay(place(root,lb),);

     splay(place(root,lb+len+),root);

     spc=tr[tr[root].rs].ls;

     if(tr[spc].hax==a1)

         return true;

     return false;

 }

 int main()

 {

     scanf("%s",lne+);

     n=strlen(lne+);

     mal[]=;

     for(int i=;i<N;i++)

     {

         mal[i]=mal[i-]*M;

         a[i]=lne[i];

     }

     scanf("%d",&m);

     build(,n+,root,);

     while(m--)

     {

         scanf("%s",cmd);

         if(cmd[]=='Q')

         {

             int sa,sb;

             scanf("%d%d",&sa,&sb);

             int ans=;

             int l,r;

             l=;r=siz-;

             while(l<=r)

             {

                 int mid=(l+r)>>;

                 if(LCQ(sa,sb,mid))

                 {

                     l=mid+;

                     ans=mid;

                 }else

                     r=mid-;

             }

             printf("%d\n",ans);

         }else if(cmd[]=='R')

         {

             int pos;

             scanf("%d",&pos);

             scanf("%s",cmd);

             splay(place(root,pos+),);

             tr[root].val=cmd[];

             pushup(root);

         }else if(cmd[]=='I')

         {

             siz++;

             n++;

             int pos;

             scanf("%d",&pos);

             scanf("%s",cmd);

             splay(place(root,pos+),);

             splay(place(root,pos+),root);

             int spc=tr[root].rs;

             tr[siz].val=cmd[];

             tr[siz].fa=spc;

             tr[spc].ls=siz;

             pushup(siz);

             pushup(spc);

             pushup(root);

         }

     }

     return ;

 }