mydcwfy's Blog

LOJ2720 [NOI2018]你的名字

Posted on
Symbols count in article: 4.5k Reading time ≈ 10 mins.

现在才来补 NOI 经典题 /kk

题意：给定一个串 $S$，$q$ 次询问，每次给出 $T, l, r$，问 $T$ 中不是 $S[l\to r]$ 的子串的本质不同子串个数。$|S|, q, |T|\leq 5\times 10 ^ 5$，$\sum |T|\leq 10 ^ 6$，4s。

考虑 $l = 1, r = n$ 怎么做。由于是求本质不同的串，考虑对 $T$ 建后缀自动机，对于每个节点统计答案。

还是要建 $S$ 的后缀自动机，然后把每一个前缀的最大匹配后缀找出来，于是这些不合法后缀的后缀都是不合法的，其他的都是合法的。

找到该前缀在 $T$ 的后缀自动机中对应的位置，那么一个节点的最大覆盖长度就是 parent 树子树下的覆盖长度的最大值。在 parent 树上做做就可以做到单次 $O(|T|)$ 的复杂度。

下面考虑 $S$ 有 $[l, r]$ 该如何计算。现在我们计算一个前缀是否能匹配，不再是看一个点有没有 ch[c] 这个儿子，还需要看 ch[c] 这个儿子有没有出现在 $[l, r]$ 区间完整出现。注意到我们相当于是看 $\text{endpos}$ 是否在 $[l + len - 1, r]$ 区间出现过。而维护每一个节点的 $\text{endpos}$，可以使用线段树合并做到 $O(|S|\log|S|)$ 的时空复杂度，单次 $O(\log|S|)$ 查询。

于是本题可以做到 $O(|S|\log|S| + \sum|T|\log|S|)$，可以通过。实现的时候注意 parent 树统计子树答案的时候用 bfs 拓扑序算而不是 dfs。另外，匹配的时候需要每一个 $len$ 都判一遍，而不是像直接跳到父亲，单次减少的 $len$ 比较大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
struct SAM {
	struct Node {
		int ch[26], len, fa;
	} tr[N << 1];
	int ls, tot, pos[N << 1], cov[N << 1];
	
	void init() { ls = tot = 1, tr[1] = {}; }
	
	void extend(int c, int curpos)
	{
		int p = ls, np = ++ tot;
		tr[np] = {}, pos[np] = curpos, ls = tot, tr[np].len = tr[p].len + 1;
		for (; p && !tr[p].ch[c]; p = tr[p].fa) tr[p].ch[c] = np;
		if (!p) tr[np].fa = 1;
		else {
			int q = tr[p].ch[c];
			if (tr[q].len == tr[p].len + 1) tr[np].fa = q;
			else {
				int nq = ++ tot;
				pos[nq] = 0, tr[nq] = tr[q], tr[nq].len = tr[p].len + 1;
				tr[np].fa = tr[q].fa = nq;
				for (; p && tr[p].ch[c] == q; p = tr[p].fa) tr[p].ch[c] = nq;
			}
		}
	}
	
	LL Twork()
	{
		for (int i = 1; i <= tot; ++ i) g[i].clear();
		for (int i = 2; i <= tot; ++ i) g[tr[i].fa].push_back(i);
		int hh = 1, tt = 1;
		q[1] = 1;
		while (hh <= tt)
		{
			int x = q[hh ++];
			for (int v : g[x])
				q[++ tt] = v;
		}
		LL res = 0;
		for (int i = tt, x; i > 1; -- i)
		{
			x = q[i];
			for (int v : g[x])
				chkmax(cov[x], cov[v]);
			// std::cout << x << ' ' << cov[x] << ' ' << tr[x].len << ' ' << tr[tr[x].fa].len << std::endl;
			if (cov[x] <= tr[x].len)
				res += tr[x].len - std::max(cov[x], tr[tr[x].fa].len);
		}
		return res;
	}
} sams, samt;

struct Node {
	int lc, rc, cnt;
} tr[(int) 3e7];

int merge(int p, int q, int l, int r)
{
	if (!p || !q) return p | q;
	int cur = ++ tot, mid = (l + r) >> 1;
	if (l == r) return tr[cur].cnt = tr[p].cnt + tr[q].cnt, cur;
	tr[cur].lc = merge(tr[p].lc, tr[q].lc, l, mid);
	tr[cur].rc = merge(tr[p].rc, tr[q].rc, mid + 1, r);
	tr[cur].cnt = tr[tr[cur].lc].cnt + tr[tr[cur].rc].cnt;
	return cur;
}

void insert(int &rt, int l, int r, int pos)
{
	if (!rt) rt = ++ tot;
	if (l == r) return void(tr[rt].cnt ++);
	int mid = (l + r) >> 1;
	if (pos <= mid) insert(tr[rt].lc, l, mid, pos);
	else insert(tr[rt].rc, mid + 1, r, pos);
	tr[rt].cnt = tr[tr[rt].lc].cnt + tr[tr[rt].rc].cnt;
}

int findlast(int x, int l, int r, int ql, int qr)
{
	if (!x || l > qr || r < ql) return 0;
	if (l == r) return l;
	int t, mid = (l + r) >> 1;
	if ((t = findlast(tr[x].rc, mid + 1, r, ql, qr))) return t;
	else return findlast(tr[x].lc, l, mid, ql, qr);
}

void work()
{
	int L, R, m;
	scanf("%s%d%d", s + 1, &L, &R);
	samt.init();
	for (m = 1; s[m]; ++ m) samt.extend(s[m] - 'a', m);
	-- m;
	for (int i = 1, u = 1, len = 0; i <= m; ++ i)
	{
		int c = s[i] - 'a', cur = 0;
		while ((!sams.tr[u].ch[c] || (cur = findlast(rt[sams.tr[u].ch[c]], 1, n, L, R)) < L + len)
			&& len)
		{
			if ((-- len) <= sams.tr[sams.tr[u].fa].len) u = sams.tr[u].fa;
		}
		// std::cout << u << std::endl;
		
		if (sams.tr[u].ch[c] && findlast(rt[sams.tr[u].ch[c]], 1, n, L, R) >= L + len)
			len ++, u = sams.tr[u].ch[c];
		mxlen[i] = len;
		// std::cout << i << ' ' << len << ' ' << cur << ' ' << u << ' ' << c << '\n';
	}
	for (int i = 1; i <= samt.tot; ++ i)
		if (samt.pos[i]) samt.cov[i] = mxlen[samt.pos[i]];
		else samt.cov[i] = 0;
	std::cout << samt.Twork() << '\n';
}

int main()
{
#ifndef Fly727
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
#endif
	scanf("%s", s + 1);
	sams.init();
	for (n = 1; s[n]; ++ n) sams.extend(s[n] - 'a', n);
	-- n;
	for (int i = 2; i <= sams.tot; ++ i) g[sams.tr[i].fa].push_back(i);
	int hh = 1, tt = 1;
	q[1] = 1;
	while (hh <= tt)
	{
		int x = q[hh ++];
		for (int v : g[x])
			q[++ tt] = v;
	}
	// std::cout << "Check " << sams.tr[4].ch[0] << std::endl;
	// for (int i = 2; i <= sams.tot; ++ i) printf("%d ", sams.pos[i]);
	// puts("");
	for (int i = tt, x; i; -- i)
	{
		x = q[i];
		if (sams.pos[x]) insert(rt[x], 1, n, sams.pos[x]);
		rt[sams.tr[x].fa] = merge(rt[sams.tr[x].fa], rt[x], 1, n);
	}
	int T;
	std::cin >> T;
	while (T --) work();
	return 0;
}