Description
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：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函数的值。
Input
第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操作有3种，如下所示： 1、 询问。语法：Q x y，x, y均为正整数。功能：计算LCQ(x, y) 限制：1 <= x, y <= 当前字符串长度。 2、 修改。语法：R x d，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字符串长度。 3、 插入：语法：I x d，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x = 0，则在字符串开头插入。限制：x不超过当前字符串长度。
Output
对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
Sample Input
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11
Sample Output
1
0
2
1
HINT
数据规模：
对于100%的数据，满足：
1、 所有字符串自始至终都只有小写字母构成。
2、 M <= 150,000
3、 字符串长度L自始至终都满足L <= 100,000
4、 询问操作的个数不超过10,000个。
对于第1，2个数据，字符串长度自始至终都不超过1,000
对于第3，4，5个数据，没有插入操作。
Source
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; #define rhl 37
#define maxl 100010
#define maxm 150010
char s[maxl]; int len;
unsigned long long mi[maxl+maxm]; struct SPLAY
{
int ch[maxl+maxm][],fa[maxl+maxm],size[maxl+maxm],key[maxl+maxm],cnt,root;
unsigned long long hash[maxl+maxm]; inline void updata(int x)
{
size[x] = size[ch[x][]] + size[ch[x][]] + ;
hash[x] = hash[ch[x][]] * mi[size[ch[x][]]+] + mi[size[ch[x][]]] * (key[x]) + hash[ch[x][]];
} inline void rotate(int x)
{
int y = fa[x],z = fa[y],l,r;
if (ch[y][] == x) l = ; else l = ; r = l ^ ;
if (z != )
{
if (ch[z][] == y) ch[z][] = x; else ch[z][] = x;
}
fa[x] = z; fa[y] = x; fa[ch[x][r]] = y;
ch[y][l] = ch[x][r]; ch[x][r] = y;
updata(y); updata(x);
fa[] = ; ch[][] = ch[][] = ;
} inline void splay(int x,int aim)
{
int t = fa[aim];
while (fa[x] != t)
{
int y = fa[x],z = fa[y];
if (fa[y] != t)
{
if ((ch[y][] == x)^(ch[z][] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if (aim == root) root = x;
} inline int find(int rank,int have,int now)
{
if (size[ch[now][]]+have+==rank) return now;
if (size[ch[now][]]+have+ > rank) return find(rank,have,ch[now][]);
else return find(rank,have+size[ch[now][]]+,ch[now][]);
} inline void init(int l,int r,int f)
{
int p; cnt = ; root = ;
build(l,r,f);
p = find(len,,root);
splay(p,root);
fa[++cnt] = p;
ch[p][] = cnt;
key[cnt] = ;
size[cnt] = ;
updata(p);
p = find(,,root);
splay(p,root);
fa[++cnt] = p;
ch[p][] = cnt;
key[cnt] = ;
size[cnt] = ;
updata(p);
} inline void build(int l,int r,int f)
{
fa[++cnt] = f;
if (l == r)
{
key[cnt] = s[l-] - 'a' + ;
hash[cnt] = key[cnt];
size[cnt] = ;
return;
}
int mid = (l+r)>>,now = cnt;
key[now] = s[mid-] - 'a' + ;
if (mid > l)
{
ch[now][] = cnt + ;
build(l,mid - ,now);
}
if (mid < r)
{
ch[now][] = cnt+;
build(mid+,r,now);
}
updata(now);
} inline void change(int a,char b)
{
int p = find(a+,,root);
splay(p,root);
key[p] = b-'a'+;
updata(p);
} inline void insert(int a,char b)
{
int p = find(a+,,root),q = find(a+,,root);
splay(p,root);
splay(q,ch[p][]);
fa[++cnt] = q;
ch[q][] = cnt; key[cnt] = b-'a'+;
updata(cnt);
updata(q);
updata(p);
} inline unsigned long long calc(int a,int b)
{
int p = find(a,,root),q = find(b+,,root);
splay(p,root);
splay(q,ch[p][]);
return hash[ch[q][]];
}
}tree; inline int ask(int a,int b)
{
int l = ,r = min(len-a+,len-b+),mid;
while (l <= r)
{
mid = (l + r) >> ;
unsigned long long h1 = tree.calc(a,a+mid-),h2 = tree.calc(b,b+mid-);
if (h1 == h2)
l = mid+;
else r = mid - ;
}
return r;
} inline void ready()
{
mi[] = ;
for (int i = ;i < maxl+maxm;++i)
mi[i] = rhl*mi[i-];
} inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} int main()
{
freopen("1014.in","r",stdin);
freopen("1014.out","w",stdout);
scanf("%s",s); len = strlen(s);
ready();
tree.init(,len,);
int T = read(); char opt;
while (T--)
{
scanf("%c",&opt);
if (opt == 'Q')
{
int a = read(),b = read();
printf("%d\n",ask(a,b));
}
else if (opt == 'R')
{
int a = read(); char b; scanf("%c\n",&b);
tree.change(a,b);
}
else
{
int a = read(); char b; scanf("%c\n",&b);
tree.insert(a,b); ++len;
}
}
fclose(stdin); fclose(stdout);
return ;
}