跳至主要內容

[Medium] P7361 「JZOI-1」拜神

xiezheyuan2025/2/9做题笔记后缀自动机线段树可持久化启发式合并约 1273 字大约 6 分钟

简要题意

给定一个长度为 nn 的，仅由小写英文字母构成的字符串 SS。有 qq 次询问，每次询问给出区间 [l,r][l,r]，你需要找到在 S[l,r]S[l,r] 中，出现至少两次的子串的长度最大值（允许重叠出现）。

1≤n≤5×104,1≤q≤1051\leq n\leq 5\times 10^4,1\leq q\leq 10^5。

思路

首先直接做十分困难的，不妨二分答案，转为判定性问题：S[l,r]S[l,r] 中是否存在出现至少两次的长度 ≥k\geq k 的子串。我们尝试用 SAM 解决这个问题。

利用 SAM 的话只有两个方向：endpos 等价类集合以及 LCS 性质。对于前者，每次询问一段区间，似乎会影响太多的等价类，可能难以维护，所以考虑后者。

我们用 LCS（最长公共后缀）的语言重写问题：是否存在 i,ji,j，使得 l+k−1≤i<j≤rl+k-1\leq i\lt j\leq r 且 LCS(S[1,i],S[1,j])≥k\mathrm{LCS}(S[1,i], S[1,j])\geq k。

由于 SAM 的性质，可以改写为 len(lca(pi,pj))≥k\mathrm{len}(\mathrm{lca}(p_i, p_j))\geq k，其中 pip_i 表示 S[1,i]S[1,i] 所在的等价类。

由于 len\mathrm{len} 是随着深度增加而增加，因此这个东西的性质是和深度类似的，再结合 LCA，可以考虑将所有 len(i)≥k\mathrm{len}(i)\geq k 的点 ii 激活，只有两个端点都被激活的 parent tree 树边才存在。那么原本的 parent tree 被我们割裂为一些连通块，我们询问是否存在 pi,pjp_i,p_j 位于同一个连通块中。

这个时候我们有一个神奇的想法，记 sk(i)s_k(i) 表示编号比 ii 大的最小的 jj，使得 pi,pjp_i,p_j 位于同一个连通块。如果我们可以维护出这个，那么只需要询问 sks_k 在区间 [l−k+1,r][l-k+1,r] 的最小值是否 ≤r\leq r 即可。

如何求出 sk(i)s_k(i) 呢？由于 sk(i)≤sk+1(i)s_k(i)\leq s_{k+1}(i)，所以可以先从 sk(i)s_k(i) 继承答案，维护将 k←k+1k\gets k+1 造成的连通块合并。这个可以并查集。

为了维护 sk(i)s_k(i)，我们给每个连通块的根节点附上当前连通块内的前缀节点集合，那么只需要启发式合并集合，在启发式合并时询问一个位置左侧和右侧第一个元素，进行修改即可。

由于需要维护出 sk(i)s_k(i)，并且 sk(i)s_k(i) 是从 sk+1(i)s_{k+1}(i) 继承得到，且最后需要维护 RMQ，于是可以考虑用可持久化线段树来维护全体 sk(i)s_k(i)。

时间复杂度 O(nlog⁡2n)O(n\log^2 n)，默认 n,qn,q 同阶。这个做法是在线的。

代码

#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