最初以为是splay维护Hash的简单题。顺手开心地敲了个splay还是指针版的。
然后发现tle了。
然后知道了可以暴力重新建串。
然后拿splay暴力重新建串。
然后又tle了。
然后不得已改成了随机线性存取表，过之。
我还是太naive了啊。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long qw;
#define _l (long long int)
const int maxn = 200009;
const int base = 233;
struct str {
char a[maxn];
int len;
inline str() {
len = 0;
}
inline void read() {
scanf("%s", a + 1);
len = strlen(a + 1);
}
inline char operator [](const int& x) const {
return a[x];
}
void ins(int p0, char* b) {
int la = strlen(b);
len += la;
for (int i = len; i >= p0 + la; -- i)
a[i] = a[i - la];
for (int i = 0; i < la; ++ i)
a[p0 + i] = b[i];
}
void chg(int x, int y, char* b) {
for (int i = 0; i + x <= y; ++ i)
a[x + i] = b[i];
}
void ers(int x, int y) {
int dl = y - x + 1;
len -= dl;
for (int i = x; i <= len; ++ i)
a[i] = a[i + dl];
}
};
int n, q, len;
qw pbb[maxn], hb[maxn];
char a[maxn];
int csp = 0;
str t;
void pre() {
pbb[0] = 1;
for (int i = 1; i < maxn; ++ i)
pbb[i] = pbb[i - 1] * base;
}
void ref() {
len = t. len;
hb[0] = 0;
for (int i = 1; i <= len; ++ i)
hb[i] = hb[i - 1] * base + t[i];
}
qw grange(int l, int r) {
return hb[r] - hb[l - 1] * pbb[r - l + 1];
}
int qry(int a, int b) {
if (t[a] != t[b])
return 0;
int l = 1, r = len - max(a, b) + 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (grange(a, a + mid - 1) == grange(b, b + mid - 1))
l = mid;
else
r = mid - 1;
}
return l;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("b2105.in", "r", stdin);
freopen("b2105.out", "w", stdout);
#endif
pre();
scanf("%d%d", &n, &q);
t. read();
ref();
while (q --) {
char opt[10];
int x, y;
scanf("%s", opt);
if (opt[0] == 'L') {
scanf("%d%d", &x, &y);
printf("%d\n", qry(x, y));
}
else if (opt[0] == 'A') {
scanf("%d%s", &x, a);
t. ins(x, a);
ref();
}
else if (opt[0] == 'C') {
scanf("%d%d%s", &x, &y, a + 1);
t. chg(x, y, a + 1);
ref();
}
else if (opt[0] == 'D') {
scanf("%d%d", &x, &y);
t. ers(x, y);
ref();
}
}
}