Loj 6041 事情的相似度

Posted on | Views:

SAM + dsu on tree + 线段树.

把后缀树建出来,每个前缀对应了后缀树上某个节点,询问 $[l,r]$ 的答案就是问 $[l,r]$ 内两两 LCA 中的最大 $\rm maxlen$ .

把询问离线下来,在后缀树上枚举 LCA,对它的子树做一个 dsu on tree,用 set 维护子树中所有前缀(按长度排序).

某个前缀与 set 中其他前缀的 LCA 都是我们枚举的点,只需要考虑长度是它的前驱后继的两个前缀的贡献就足够了.

于是我们可以得到若干个三元组 $(x,y,d)$ 表示前缀 $x$ 与前缀 $y$ ( $x<y$ ) 的 LCS 是 $d$ .

将三元组按 $y$ 从小到大排序,从小到大枚举 $r$ ,用线段树维护每个 $l$ 的答案即可.

时间复杂度 $O(n\log^2 n)$ .

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int N = 2e5 + 10;
int n, m;
int idx = 1, lst = 1, ch[N][2], fa[N], len[N], siz[N], pos[N], mxson[N];
vector<int> G[N];
void Extend(int c, int x)
{
	int np = ++idx, p = lst;
	lst = np;
	len[np] = len[p] + 1;
	while (p && !ch[p][c])
		ch[p][c] = np, p = fa[p];
	if (!p)
		fa[np] = 1;
	else
	{
		int q = ch[p][c];
		if (len[q] == len[p] + 1)
			fa[np] = q;
		else
		{
			int nq = ++idx;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q];
			fa[q] = fa[np] = nq;
			memcpy(ch[nq], ch[q], sizeof ch[nq]);
			while (p && ch[p][c] == q)
				ch[p][c] = nq, p = fa[p];
		}
	}
	pos[np] = x;
}
char buf[N];
set<int> s;
int dep[N];
void init(int u)
{
	siz[u] = 1;
	for (int v : G[u])
	{
		dep[v] = dep[u] + 1;
		init(v);
		if (!mxson[u] || siz[v] > siz[mxson[u]])
			mxson[u] = v;
		siz[u] += siz[v];
	}
}
struct info
{
	int x, y, d;
	bool operator < (const info &rhs) const
	{
		return y == rhs.y ? d > rhs.d : y < rhs.y;
	}
} q[N * 30], p[N];
int tot = 0;
void calc(int x, int d)
{
	if (!x || s.empty() || !d)
		return;
	auto it = s.lower_bound(x);
	if (it != s.end())
		q[++tot] = (info){x, *it, d};
	if (it != s.begin())
		q[++tot] = (info){*(--it), x, d};
}
void Calc(int u, int d)
{
	calc(pos[u], d);
	for (int v : G[u])
		Calc(v, d);
}
void add(int x)
{
	if (x)
		s.insert(x);
}
void Add(int u)
{
	add(pos[u]);
	for (int v : G[u])
		Add(v);
}
void dfs(int u, bool flag)
{
	for (int v : G[u])
		if (v != mxson[u])
			dfs(v, false);
	if (mxson[u])
		dfs(mxson[u], true);
	calc(pos[u], len[u]);
	add(pos[u]);
	for (int v : G[u])
		if (v != mxson[u])
		{
			Calc(v, len[u]);
			Add(v);
		}
	if (!flag)
		s.clear();
}
int ans[N], mx[N << 1];
void upd(int o, int l, int r, int L, int R, int c)
{
	if (L <= l && r <= R)
	{
		mx[o] = max(mx[o], c);
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid)
		upd(o << 1, l, mid, L, R, c);
	if (R > mid)
		upd(o << 1 | 1, mid + 1, r, L, R, c);
}
void query(int &res, int o, int l, int r, int pos)
{
	res = max(res, mx[o]);
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	if (pos <= mid)
		query(res, o << 1, l, mid, pos);
	else
		query(res, o << 1 | 1, mid + 1, r, pos);
}
int main()
{
	n = read(), m = read();
	scanf("%s", buf + 1);
	for (int i = 1; i <= n; ++i)
		Extend(buf[i] - '0', i);
	for (int i = 2; i <= idx; ++i)
		G[fa[i]].push_back(i);
	init(1);
	dfs(1, true);
	for (int i = 1; i <= m; ++i)
	{
		int l = read(), r = read();
		p[i] = (info){l, r, i};
	}
	sort(q + 1, q + 1 + tot);
	sort(p + 1, p + 1 + m);
	for (int r = 1, i = 1, j = 1; r <= n; ++r)
	{
		while (i <= tot && q[i].y == r)
			upd(1, 1, n, 1, q[i].x, q[i].d), ++i;
		while (j <= m && p[j].y == r)
			query(ans[p[j].d], 1, 1, n, p[j].x), ++j;
	}
	for (int i = 1; i <= m; ++i)
		printf("%d\n", ans[i]);
	return 0;
}