题解：P7361 「JZOI-1」拜神
xiezheyuan
·
·
题解
简要题意
给定一个长度为 n 的，仅由小写英文字母构成的字符串 S。有 q 次询问，每次询问给出区间 [l,r]，你需要找到在 S[l,r] 中，出现至少两次的子串的长度最大值（允许重叠出现）。
## 思路
首先直接做十分困难的，不妨二分答案，转为判定性问题：$S[l,r]$ 中是否存在出现至少两次的长度 $\geq k$ 的子串。我们尝试用 SAM 解决这个问题。
利用 SAM 的话只有两个方向：endpos 等价类集合以及 LCS 性质。对于前者，每次询问一段区间，似乎会影响太多的等价类，可能难以维护，所以考虑后者。
我们用 LCS（最长公共后缀）的语言重写问题：是否存在 $i,j$，使得 $l+k-1\leq i\lt j\leq r$ 且 $\mathrm{LCS}(S[1,i], S[1,j])\geq k$。
由于 SAM 的性质，可以改写为 $\mathrm{len}(\mathrm{lca}(p_i, p_j))\geq k$，其中 $p_i$ 表示 $S[1,i]$ 所在的等价类。
由于 $\mathrm{len}$ 是随着深度增加而增加，因此这个东西的性质是和深度类似的，再结合 LCA，可以考虑将所有 $\mathrm{len}(i)\geq k$ 的点 $i$ 激活，只有两个端点都被激活的 parent tree 树边才存在。那么原本的 parent tree 被我们割裂为一些连通块，我们询问是否存在 $p_i,p_j$ 位于同一个连通块中。
这个时候我们有一个神奇的想法，记 $s_k(i)$ 表示编号比 $i$ 大的最小的 $j$，使得 $p_i,p_j$ 位于同一个连通块。如果我们可以维护出这个，那么只需要询问 $s_k$ 在区间 $[l-k+1,r]$ 的最小值是否 $\leq r$ 即可。
如何求出 $s_k(i)$ 呢？由于 $s_k(i)\leq s_{k+1}(i)$，所以可以先从 $s_k(i)$ 继承答案，维护将 $k\gets k+1$ 造成的连通块合并。这个可以并查集。
为了维护 $s_k(i)$，我们给每个连通块的根节点附上当前连通块内的前缀节点集合，那么只需要启发式合并集合，在启发式合并时询问一个位置左侧和右侧第一个元素，进行修改即可。
由于需要维护出 $s_k(i)$，并且 $s_k(i)$ 是从 $s_{k+1}(i)$ 继承得到，且最后需要维护 RMQ，于是可以考虑用可持久化线段树来维护全体 $s_k(i)$。
时间复杂度 $O(n\log^2 n)$，默认 $n,q$ 同阶。这个做法是在线的。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
template<int N, int MAX_CHAR>
struct SuffixAutomaton {
int trans[N << 1][MAX_CHAR], link[N << 1], len[N << 1], cur, tot;
int cnt, lst[N << 1], per[N <<1];
vector<int> ptr[N << 1];
SuffixAutomaton(){ link[0] = -1; }
void extend(int c){
int x = cur; cur = ++tot;
len[cur] = len[x] + 1;
lst[cur] = ++cnt, per[cnt] = cur;
for(;(~x)&&(!trans[x][c]);x=link[x]) trans[x][c] = cur;
if(!(~x)) return link[cur] = 0, void();
int y = trans[x][c];
if(len[y] == len[x] + 1) return link[cur] = y, void();
int u = ++tot, d = y;
link[u] = link[y], link[d] = link[cur] = u, len[u] = len[x] + 1;
for(int i=0;i<MAX_CHAR;i++) trans[u][i] = trans[d][i];
for(;(~x)&&(trans[x][c]==y);x=link[x]) trans[x][c] = u;
}
void build(){
for(int i=1;i<=tot;i++) ptr[link[i]].push_back(i);
}
};
const int N = 5e4 + 5;
SuffixAutomaton<N, 26> sam;
int n, q;
string s;
vector<int> len[N];
struct node{
int l, r, v, ver;
} t[N << 5];
int rt[N], tot;
void update(int p, int v, int ver, int &i, int l, int r){
if(t[i].ver != ver) t[++tot] = t[i], t[tot].ver = ver, i = tot;
if(l == r) return t[i].v = v, void();
int mid = (l + r) >> 1;
if(p <= mid) update(p, v, ver, t[i].l, l, mid);
else update(p, v, ver, t[i].r, mid + 1, r);
t[i].v = min(t[t[i].l].v, t[t[i].r].v);
}
int query(int ql, int qr, int i, int l, int r){
if(ql <= l && r <= qr) return t[i].v;
int mid = (l + r) >> 1;
int ans = INT_MAX;
if(ql <= mid) ans = min(ans, query(ql, qr, t[i].l, l, mid));
if(mid < qr) ans = min(ans, query(ql, qr, t[i].r, mid + 1, r));
return ans;
}
int fa[N << 1];
set<int> st[N << 1];
int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y, int ver){
x = find(x), y = find(y);
if(x == y) return;
if(st[x].size() < st[y].size()) swap(x, y);
fa[y] = x;
for(int i : st[y]){
auto ite = st[x].upper_bound(i);
if(ite != st[x].end()) update(i, *ite, ver, rt[ver], 1, n);
if(ite != st[x].begin()) update(*(--ite), i, ver, rt[ver], 1, n);
st[x].insert(i);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q >> s;
for(char ch : s) sam.extend(ch - 'a');
sam.build();
for(int i=0;i<=sam.tot;i++) len[sam.len[i]].push_back(i);
iota(fa, fa + sam.tot + 1, 0);
for(int i=1;i<=n;i++) st[sam.per[i]].insert(i);
for(int i=1;i<=n;i++) update(i, n + 1, n + 1, rt[n + 1], 1, n);
for(int i=n;~i;i--){
rt[i] = rt[i + 1];
for(int j : len[i]){
for(int k : sam.ptr[j]) merge(j, k, i);
}
}
while(q--){
int l, r; cin >> l >> r;
int L = 0, R = r - l + 1;
while(L < R){
int mid = (L + R + 1) >> 1;
if(query(l + mid - 1, r, rt[mid], 1, n) <= r) L = mid;
else R = mid - 1;
}
cout << L << '\n';
}
return 0;
}
// Written by xiezheyuan
```