\(\text{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\) 函数的值。
\(\text{Input}\)
第一行给出初始的字符串。第二行是一个非负整数 \(M\) ，表示操作的个数。接下来的 \(M\) 行，每行描述一个操作。操作有 \(3\) 种，如下所示：
询问。语法：\(Q\ x\ y\) ，\(x, y\) 均为正整数。功能：计算 \(LCQ(x, y)\) 限制：\(1 <= x, y <= 当前字符串长度\) 。
修改。语法：\(R\ x\ d\) ，\(x\) 是正整数，\(d\) 是字符。功能：将字符串中第 \(x\) 个数修改为字符 \(d\) 。限制：\(x\) 不超过当前字符串长度。
插入：语法：\(I\ x\ d\) ，\(x\) 是非负整数，\(d\) 是字符。功能：在字符串第 \(x\)个字符之后插入字符 \(d\) , 如果 \(x = 0\) ，则在字符串开头插入。限制：\(x\) 不超过当前字符串长度。
\(\text{Output}\)
对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
\(\text{Sample Input}\)
madamimadam7Q 1 7Q 4 8Q 10 11R 3 aQ 1 7I 10 aQ 2 11
\(\text{Sample Output}\)
51021
数据规模：
对于 \(100%\) 的数据，满足：
1、 所有字符串自始至终都只有小写字母构成。
2、 \(M <= 150,000\)
3、 字符串长度 \(L\) 自始至终都满足 \(L <= 100,000\)
4、 询问操作的个数不超过 \(10,000\) 个。
对于第 \(1，2\) 个数据，字符串长度自始至终都不超过 \(1,000\)
对于第 \(3，4，5\) 个数据，没有插入操作。\(\text{Solution:}\)
维护一颗splay区间树，维护一个节点为根的子树中序遍历的字符串的哈希值。
求 \(LCP\) 就二分长度，然后比较。
#define ull unsigned long longconst int maxN = 5e5 + 10;const int base = 27;ull xp[maxN], H[maxN];int n, m;int fa[maxN], ch[maxN][2], val[maxN], size[maxN], Ncnt, root, sz;#define ls(x) (ch[x][0])#define rs(x) (ch[x][1])#define chk(x) (ch[fa[x]][1] == x)inline void pushup(int x) { size[x] = size[ls(x)] + size[rs(x)] + 1; H[x] = H[ls(x)] * xp[size[rs(x)] + 1] + val[x] * xp[size[rs(x)]] + H[rs(x)];}inline void rotate(int x) { int y = fa[x], z = fa[y], k = chk(x), tmp = ch[x][k ^ 1]; ch[y][k] = tmp, fa[tmp] = y; ch[z][chk(y)] = x, fa[x] = z; ch[x][k ^ 1] = y, fa[y] = x; pushup(y), pushup(x);}inline void splay(int x, int goal = 0) { int y, z; while (fa[x] != goal) { y = fa[x], z = fa[y]; if (z != goal) { if (chk(x) == chk(y)) rotate(y); else rotate(x); } rotate(x); } if (goal == 0) root = x;}inline int kth(int k) { int x = root; while (1) { if (ch[x][0] && k <= size[ls(x)]) x = ls(x); else if (size[ls(x)] + 1 < k) { k -= size[ls(x)] + 1, x = rs(x); } else return x; }}inline int split(int x, int y) { int pre = kth(x - 1), nxt = kth(y + 1); splay(pre); splay(nxt, pre); return ls(nxt);}inline void insert(int x, char str) { int pre = kth(x), nxt = kth(x + 1); splay(pre); splay(nxt, pre); int cur = ++Ncnt; ch[nxt][0] = cur; val[cur] = H[cur] = str - 'a' + 1; size[cur] = 1; fa[cur] = nxt; splay(cur);}inline ull query(int x, int L) { int cur = split(x, x + L - 1); return H[cur];}inline int solve(int x, int y) { int l = 1, r = min(sz - x, sz - y), mid, ans = 0; while (l <= r) { mid = (l + r) >> 1; if (query(x, mid) == query(y, mid)) ans = mid, l = mid + 1; else r = mid - 1; } return ans;}int build(int l, int r, char *cher) { if (l > r) return 0; int mid = (l + r) >> 1; int x = ++Ncnt; size[x] = 1; val[x] = H[x] = cher[mid] - 'a' + 1; if (ch[x][0] = build(l, mid - 1, cher)) fa[ch[x][0]] = x; if (ch[x][1] = build(mid + 1, r, cher)) fa[ch[x][1]] = x; pushup(x); return x;}char str[maxN];int main() {#ifndef ONLINE_JUDGE file("P4036");#endif xp[0] = 1; for (int i = 1; i < maxN; ++ i) xp[i] = xp[i - 1] * base; scanf("%s", str + 2); n = strlen(str + 2); sz = n + 2; root = build(1, n + 2, str); scanf("%d", &m); char op[30], s[3]; while (m --) { scanf("%s", op); if (op[0] == 'Q') { int x, y; scanf("%d%d", &x, &y); printf("%d\n", solve(x + 1, y + 1)); } else if (op[0] == 'R') { int x; scanf("%d%s", &x, s); int cur = kth(x + 1); splay(cur); val[cur] = s[0] - 'a' + 1; pushup(cur); } else { int x; scanf("%d%s", &x, s); insert(x + 1, s[0]); sz++; } }}