题目大意
对于一个小写字母组成的字符串，有 (m) 种操作。
- ( exttt{L} ext{ }x ext{ }y) ：询问分别从第 (x) 位、第 (y) 位开始的子串的最长公共前缀长度。
- ( exttt{R} ext{ }x ext{ }d) ：将第 (x) 位的字符修改为 (d) 。
- ( exttt{I} ext{ }x ext{ }d) ：在第 (x) 位后插入字符 (d) 。
其中，字符串长度 (L) 始终满足 (1 leq L leq 10^5) ，且字符串始终由小写字母组成， (1 leq n leq 1.5 imes 10^5) ，询问的操作个数不超过 (10^4) 个。
题解
容易想到，对于每一段子串可以用 Hash 进行比较。
若 ([x,x+k)) 和 ([y,y+k)) 相同，则 ([x,x+k-1)) 和 ([y,y+k-1)) 一定相同。
若 ([x,x+k)) 和 ([y,y+k)) 不相同，则 ([x,x+k+1)) 和 ([y,y+k+1)) 一定不相同。
显然我们可以用二分来做。
然而这一题还需要支持修改和插入操作，我们可以用平衡树来维护每一个点的 Hash 值。
设点 (i) 的 Hash 值为 (H(i)) ，左儿子为 (l_i) ，右儿子为 (r_i) ，子树大小为 (size(i)) ，对应的字母为 (val_i)。
则 (H(i) = H(l_i) imes base^{size(r_i)+1} + val_i imes base^{size(r_i)} + H(r_i)) 。
用 unsigned int + 自然溢出就好，取模太慢了。
代码自带大常数，开了 O2 才A。
听说 Splay 跑得比 FHQ Treap 快，但是不想打。。。
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <algorithm>
using std::swap;
#define MAX_N (100000 + 5)
#define MAX_M (150000 + 5)
struct FHQ_Treap
{
int ch[2];
int prior;
unsigned val;
unsigned hash;
int size;
};
const unsigned base = 27;
int T;
char s[MAX_N];
int n, m;
int root, len;
FHQ_Treap t[MAX_N + MAX_M];
unsigned p[MAX_N + MAX_M];
int ReadInt()
{
int res = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
return res;
}
char ReadChar()
{
char ch = getchar();
while (!isalpha(ch)) ch = getchar();
return ch;
}
int newNode(int val)
{
t[++len].prior = rand();
t[len].ch[0] = t[len].ch[1] = 0;
t[len].val = t[len].hash = val;
t[len].size = 1;
return len;
}
void Update(int idx)
{
int l = t[idx].ch[0], r = t[idx].ch[1];
t[idx].size = t[l].size + t[r].size + 1;
t[idx].hash = t[l].hash * p[t[r].size + 1] + t[idx].val * p[t[r].size] + t[r].hash;
}
void Split(int idx, int rk, int & L, int & R)
{
if (!idx)
{
L = R = 0;
return;
}
if (t[t[idx].ch[0]].size + 1 <= rk)
{
L = idx;
Split(t[idx].ch[1], rk - t[t[idx].ch[0]].size - 1, t[L].ch[1], R);
}
else
{
R = idx;
Split(t[idx].ch[0], rk, L, t[R].ch[0]);
}
Update(idx);
}
int Merge(int L, int R)
{
if (!L || !R) return L + R;
if (t[L].prior < t[R].prior)
{
t[L].ch[1] = Merge(t[L].ch[1], R);
Update(L);
return L;
}
else
{
t[R].ch[0] = Merge(L, t[R].ch[0]);
Update(R);
return R;
}
}
unsigned Query(int l, int r)
{
int L, M, R;
unsigned res;
Split(root, r, L, R);
Split(L, l - 1, L, M);
res = t[M].hash;
root = Merge(Merge(L, M), R);
return res;
}
void Modify(int rk, unsigned val)
{
int L, M, R;
Split(root, rk - 1, L, R);
Split(R, 1, M, R);
t[M].val = t[M].hash = val;
root = Merge(Merge(L, M), R);
}
void Insert(int rk, unsigned val)
{
int L, R;
Split(root, rk, L, R);
root = Merge(Merge(L, newNode(val)), R);
}
int main()
{
srand(19260817);
p[0] = 1;
for (int i = 1; i < MAX_N + MAX_M; ++i)
{
p[i] = p[i - 1] * base;
}
T = ReadInt();
while (T--)
{
root = len = 0;
scanf("%s", s + 1);
m = ReadInt();
n = strlen(s + 1);
for (int i = 1; i <= n; ++i)
{
root = Merge(root, newNode(s[i] - 'a' + 1));
}
char ch, d;
int x, y, l, r, mid, ans;
while (m--)
{
ch = ReadChar();
switch (ch)
{
case 'Q':
x = ReadInt();
y = ReadInt();
if (x > y) swap(x, y);
l = 0;
r = len - y + 1;
while (l < r)
{
mid = l + r + 1 >> 1;
if (Query(x, x + mid - 1) != Query(y, y + mid - 1)) r = mid - 1;
else l = mid;
}
printf("%d
", r);
break;
case 'R':
x = ReadInt();
d = ReadChar();
Modify(x, d - 'a' + 1);
break;
case 'I':
x = ReadInt();
d = ReadChar();
Insert(x, d - 'a' + 1);
break;
}
}
}
return 0;
}