luogu5212/bzoj2555 substring(后缀自动机+动态树)

对字符串构建一个后缀自动机.

每次查询的就是在转移边上得到节点的parent树中后缀节点数量.

由于强制在线，可以用动态树维护后缀自动机parent树的子树和。

注意一个玄学的优化：每次在执行连边操作时，让parent节点作为x，新节点作为y，否则在一串字符相同的串会被莫名其妙卡成N方。

压行后的lct和sam

#include <cstdio>

#include <cstring>

#include <map>

using namespace std;

struct node { int len, link, sz; map<char, int> next; } sam[1200010];

char tmp[3000010], tmp1[233];

int ch[1200010][2], fa[1200010], st[1200010], sz[1200010], s[1200010], mask, qcnt, tot, last;

bool lazy[1200010], val[1200010];

void decode() { for (int j = 0, mask1 = mask, len = strlen(tmp); j < len; j++) swap(tmp[j], tmp[mask1 = (mask1 * 131 + j) % len]); }

bool nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }

void rev(int x) { swap(ch[x][0], ch[x][1]), lazy[x] ^= 1; }

void pushup(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + s[x] + val[x]; }

void pushdown(int x) { if (lazy[x]) { if (ch[x][0]) { rev(ch[x][0]); } if (ch[x][1]) { rev(ch[x][1]); } lazy[x] = 0; } }

void rotate(int x)

{

	int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][k ^ 1];

	if (nroot(y)) { ch[z][ch[z][1] == y] = x; } ch[x][k ^ 1] = y, ch[y][k] = w;

	if (w) { fa[w] = y; } fa[y] = x; fa[x] = z; pushup(y), pushup(x);

}

void splay(int x)

{

	int y = x, top = 0; st[++top] = y; while (nroot(y)) { st[++top] = y = fa[y]; } while (top > 0) { pushdown(st[top--]); }

	while (nroot(x)) { int y = fa[x], z = fa[y]; if (nroot(y)) { rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y); } rotate(x); }

}

void access(int x) { for (int y = 0; x > 0; x = fa[y = x]) splay(x), s[x] += sz[ch[x][1]] - sz[y], ch[x][1] = y, pushup(x); }

void makert(int x) { access(x), splay(x), rev(x); }

int findrt(int x) { access(x), splay(x); while (ch[x][0]) { pushdown(x), x = ch[x][0]; } return x; }

void link(int x, int y) { makert(x); if (findrt(y) != x) fa[x] = y, s[y] += sz[x], pushup(y); }

void cut(int x, int y) { makert(x); if (findrt(y) == x && fa[x] == y && ch[x][1] == 0) ch[y][0] = fa[x] = 0, pushup(y); }

void insert(char ch)

{

	int cur = ++tot, p = last; sam[cur].len = sam[last].len + 1, sam[cur].sz = 1, sam[cur].next.clear(), sz[tot] = val[tot] = 1;

	while (p != -1 && sam[p].next.count(ch) == false) sam[p].next[ch] = cur, p = sam[p].link;

	if (p == -1) { sam[cur].link = 1, link(1, cur); }

	else

	{

		int q = sam[p].next[ch];

		if (sam[p].len + 1 == sam[q].len) { sam[cur].link = q, link(q, cur); }

		else

		{

			int cjh = ++tot;

			sam[cjh].len = sam[p].len + 1, sam[cjh].link = sam[q].link, link(sam[q].link, cjh), sam[cjh].next = sam[q].next;

			while (p != -1 && sam[p].next[ch] == q) sam[p].next[ch] = cjh, p = sam[p].link;

			if (sam[q].link) { cut(sam[q].link, q); } sam[q].link = sam[cur].link = cjh, link(cjh, q), link(cjh, cur);

		}

	}

	last = cur;

}

int main()

{

	tot = 1, last = 1; sam[1].len = 0, sam[1].link = -1, sam[1].sz = 1, sam[1].next.clear(), sz[tot] = val[tot] = 1;

	scanf("%d%s", &qcnt, tmp); for (int j = 0; tmp[j] != 0; j++) insert(tmp[j]);

	for (int i = 1; i <= qcnt; i++)

	{

		scanf("%s%s", tmp1, tmp), decode();

		if (!strcmp(tmp1, "ADD")) for (int j = 0; tmp[j] != 0; j++) insert(tmp[j]);

		else

		{

			int p = 1;

			for (int j = 0; tmp[j] != 0; j++)

				if (sam[p].next.count(tmp[j])) p = sam[p].next[tmp[j]];

				else { printf("0\n"); goto escape; }

			cut(p, sam[p].link), makert(p);

			int ans = sz[p];

			link(sam[p].link, p);

			printf("%d\n", ans), mask ^= ans;

		} escape:;

	}

	return 0;

}

巴特西

luogu5212/bzoj2555 substring(后缀自动机+动态树)

最新文章

热门文章