laekov

最初以为是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();

}

}

}