bzoj2555: SubString，bzoj2555substring

bzoj2555: SubString，bzoj2555substring

传送门.

算是一下复习了两个算法。

题解：

建出后缀自动机，然后相当于有删边，有加边，动态维护一个点的子树里有多少个结尾的点。

可以直接用lct维护子树和，或者ett维护。

注意一棵有根树，其实只用lct维护路径和应该是最简单的。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define x0 t[x][0]
#define x1 t[x][1]
using namespace std;

const int N = 1.2e6 + 5, M = 3e6 + 5;

int t[N][2], rev[N], z[N], lz[N], a[N], pf[N], dd[N], fa[N];
int lr(int x) {return t[fa[x]][1] == x;}
void fan(int x) { if(x) swap(x0, x1), rev[x] ^= 1;}
void add(int x, int y) {if(x) z[x] += y, lz[x] += y; }
void down(int x) {
	if(rev[x]) fan(x0), fan(x1), rev[x] = 0;
	if(lz[x]) add(x0, lz[x]), add(x1, lz[x]), lz[x] = 0;
}
void rotate(int x) {
	int y = fa[x], k = lr(x);
	t[y][k] = t[x][!k]; if(t[x][!k]) fa[t[x][!k]] = y;
	fa[x] = fa[y]; if(fa[y]) t[fa[y]][lr(y)] = x;
	fa[y] = x; t[x][!k] = y; pf[x] = pf[y];
}
void xc(int x) {
	for(; x; x = fa[x]) dd[++ dd[0]] = x;
	while(dd[0]) down(dd[dd[0] --]);
}
void splay(int x, int y) {
	xc(x);
	while(fa[x] != y) {
		if(fa[fa[x]] != y)
			if(lr(x) == lr(fa[x])) rotate(fa[x]); else rotate(x);
		rotate(x);
	}
}
void access(int x) {
	int X = x;
	for(int y = 0; x; y = x, x = pf[x])
		splay(x, 0), fa[t[x][1]] = 0, pf[t[x][1]] = x,
		t[x][1] = y, fa[y] = x, pf[y] = 0;
	splay(X, 0);
}
void makeroot(int x)  {	access(x); fan(x);}
void link(int x, int y) {
	splay(x, 0); makeroot(1); access(y); add(y, z[x]);
	makeroot(x), pf[x] = y;
}
void cut(int x, int y) {
	splay(x, 0); makeroot(1); access(y); add(y, -z[x]);
	makeroot(x); access(y);
	t[y][0] = fa[x] = pf[x] = 0;
}

struct suffix_automation {
	int son[N][26], fa[N], dep[N], tot, la;
	void b() { tot = la = 1;}
	#define push(v) dep[++ tot] = v
	void ad(int c) {
		push(dep[la] + 1);
		int p = la, np = tot;
		for(; p && !son[p][c]; p = fa[p]) son[p][c] = np;
		if(!p) link(np, 1), fa[np] = 1; else {
			int q = son[p][c];
			if(dep[q] > dep[p] + 1) {
				push(dep[p] + 1); int nq = tot;
				memcpy(son[nq], son[q], sizeof son[q]);
				link(nq, fa[q]);
				fa[nq] = fa[q];
				cut(q, fa[q]); link(q, nq); link(np, nq);
				fa[q] = fa[np] = nq;
				for(; son[p][c] == q; p = fa[p]) son[p][c] = nq;
			} else link(np, q), fa[np] = q;
		}
		la = np;
		makeroot(1); access(la); add(la, 1);
	}
} suf;

int Q, len, mask, ans; char s[M], tp[10];

int main() {
	suf.b();
	scanf("%d", &Q);
	scanf("%s", s); len = strlen(s);
	fo(j, 0, len - 1) suf.ad(s[j] - 'A');
	fo(ii, 1, Q) {
		scanf("%s %s", tp, s); len = strlen(s);
		int M = mask;
		fo(j, 0, len - 1) M = (M * 131 + j) % len, swap(s[j], s[M]);
		if(tp[0] == 'A') {
			fo(j, 0, len - 1) suf.ad(s[j] - 'A');
		} else {
			int x = 1;
			fo(j, 0, len - 1) x = suf.son[x][s[j] - 'A'];
			if(x) splay(x, 0), ans = z[x]; else ans = 0;
			printf("%d\n", ans);
			mask ^= ans;
		}
	}
}