题解：P10716 【MX-X1-T4】「KDOI-05」简单的字符串问题

· · 题解

刻画一下合法的 A。

首先 A 是 S[1,i] 的一个 border。

然后 A 应该在前缀 [1,i] 中不重复地出现 k 次。

考虑从第二个限制入手，你发现 A 是原序列一个前缀，而一个前缀 S[1,j] 至多不重复地出现 \frac{n}{j} 次。

不妨记 dp_{i,j} 表示前缀 S[1,i] 第一次满足其不重复地出现 j 次的位置，根据上面的分析状态总量是 O(n \log n) 的，查询就是找 i 在 fail 树上的祖先中所有满足 dp_{x,k} \leq i 的祖先。

注意到假若串 A 可以满足条件的话，A 的任意 border 一定也满足条件，因此满足条件的祖先一定是 i 到根上链的上半段，假若能处理出所有 dp_{i,j} 就可以通过树上倍增把这段找出来。

处理 dp_{i,j} 可以考虑在 fail 树上 dfs，对于每个点 u 维护其子树内所有点代表的前缀，这些前缀就是这个点 u 代表的前缀所有出现位置的结束位置构成的集合，你可以考虑 set 启发式合并来维护这个集合，处理 dp 数组时由于 dp 数组状态总量是 O(n \log n) 的所以直接暴力找后继处理即可做到 O(n \log^2 n + q \log n)。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define lowbit(x) (x&(-x))
//#define bp push_back
//#define sz size
//#define cl clear
const int maxn = 2e5+114;
int n,q;
char c[maxn];
int nxt[maxn];
vector<int> E[maxn];
set<int> S[maxn];
vector<int> dp[maxn];
int fa[maxn][20];
int dep[maxn];
void dfs(int u){
    S[u].insert(u);
    for(int v:E[u]){
        dep[v]=dep[u]+1;
        fa[v][0]=u;
        for(int i=1;i<19;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
        dfs(v);
        if(S[v].size()>S[u].size()) swap(S[u],S[v]);
        for(int x:S[v]) S[u].insert(x);
    }
    if(u==0) return ;
    dp[u].push_back(0);
    dp[u].push_back(u);
    int st=u+u;
    while(S[u].lower_bound(st)!=S[u].end()){
        dp[u].push_back((*S[u].lower_bound(st)));
        st=dp[u].back()+u;
    }
}
int answer[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=2;i<=n;i++){
        int z=nxt[i-1];
        while(c[z+1]!=c[i]&&z!=0) z=nxt[z];
        if(c[z+1]==c[i]) z++;
        nxt[i]=z;
    }
    for(int i=1;i<=n;i++) E[nxt[i]].push_back(i);
    dfs(0);
    cin>>q;
    for(int i=1;i<=q;i++){
        int l,k;
        cin>>l>>k;
        if(k==1) cout<<1<<'\n';
        else{
            int u=l;
            for(int i=19;i>=0;i--){
                if(fa[u][i]!=0&&((dp[fa[u][i]].size()-1<k)||(dp[fa[u][i]][k]>l))) u=fa[u][i];
            }
            cout<<dep[fa[u][0]]<<'\n';          
        }
    }
    return 0;
}
/*
10
aabaacaaaa
1
10 5
*/