LGP7046 「MCOI-03」诗韵 - Sol

zls_XICK · 2026-11-13 19:41:35 · 题解

Preface

很快想到个自然的解法，然后卡常了一个下午（其它解法应该没这么卡）。

::::info[卡常记录（部分）] ::::

思路和 [@if_miao]() 大佬类似的，选择用 SAM 与线段树合并解决这个东西。

Sol

题意就是对于每次新加入的区间，问有多少个子串满足是 >K 个区间的后缀（重复子串只算一次），以及最长后缀长度。

我们建 SAM 后可以得到每个下标在 SAM 里对应的位置（记为 pos_i），那么对于一个查询区间 \left[l,r\right]，长度 len=r-l+1，我们便可以从 pos_r 开始沿着 link 往前跳到最后一个一个 endpos 最长串长度 \geq len 的位置，把询问存在这（此时 \left[l,r\right] 这个区间就在这个 endpos 里了）。

跳 link 用倍增预处理（记 fa_{j,i} 为 i 向前跳 2^j 个 link 的位置）可以做到 O\left(n \log n\right)，这是个经典处理。

然后考虑怎么计算答案，由于 x 为 y 到根节点 link 链上的点时，x 对应的 endpos 都是 y 对应 endpos 的后缀，所以答案统计从子树转移来，考虑线段树合并。

同一 endpos 中，按长度总大到小处理（因为显然长度小的是长度大的后缀），由于重复子串只记一次，同一长度时贪心地只记录询问最靠前的那个区间，把它单点加入线段树中，这样如果线段树内可以查到第 K+1 小的位置（这里的位置指询问的下标），那么从这之后的串（显然都更短）都可以作为 >K 个区间的后缀，累计答案即可。

比较显然的是累计答案我们不可能每个都加，这里差分一下就行（和前面贪心记最小下标配合，所以不会漏）。

这个做法是 O\left(\left(n+m\right)\log\left(n+m\right)\right) 的，但是常数比较大，所以卡常。

然后另一个细节是询问的重复区间无效，在这个做法中，set<pair<int,int>>、map<pair<int,int>,bool> 都很慢，会 TLE 一个点，应该把询问排序后，重复的只保留下标靠前的。

::::success[AC Code]

#include <bits/stdc++.h>
#define zls rp++
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
using namespace std;
const ll inf=2e18;
const ll md=1e9+7;
const double eps=1e-12;
struct node{
    int pre,len;
    int nx[30];
}p[1000005];
int n,m,k,id=0,lst=0;
string s;
void add(int x){
    int op=++id,l=lst;
    p[op].len=p[l].len+1;
    while(l!=-1&&!p[l].nx[x]){
        p[l].nx[x]=op;
        l=p[l].pre;
    }
    if(l==-1)p[op].pre=0;
    else{
        int v=p[l].nx[x];
        if(p[v].len==p[l].len+1)p[op].pre=v;
        else{
            int cp=++id;
            p[cp]=p[v];
            p[cp].len=p[l].len+1;
            while(l!=-1&&p[l].nx[x]==v){
                p[l].nx[x]=cp;
                l=p[l].pre;
            }
            p[op].pre=p[v].pre=cp;
        }
    }
    lst=op;
}
int pos[500005],fa[25][1000005];
vector<int>e[1000005];
vector<pii>ques[1000005];
int rt[1000005],mx[500005],t=0;
ll ans[500005];
struct tree{
    int ls,rs;
    int sum;
}tr[30000005];
int merge(int lx,int rx,int l,int r){
    if(!lx)return rx;
    if(!rx)return lx;
    if(l==r){
        tr[lx].sum|=tr[rx].sum;
        return lx;
    }
    int mid=(l+r)/2;
    tr[lx].ls=merge(tr[lx].ls,tr[rx].ls,l,mid);
    tr[lx].rs=merge(tr[lx].rs,tr[rx].rs,mid+1,r);
    tr[lx].sum=tr[tr[lx].ls].sum+tr[tr[lx].rs].sum;
    return lx;
}
int query(int x,int l,int r,int K){
    if(tr[x].sum<K)return 0;
    if(l==r)return l;
    int mid=(l+r)/2,lsum=tr[tr[x].ls].sum;
    if(lsum>=K)return query(tr[x].ls,l,mid,K);
    else return query(tr[x].rs,mid+1,r,K-lsum);
}
int add(int x,int l,int r,int pos){
    if(!x)x=++t;
    if(l==r){
        tr[x].sum|=1;
        return x;
    }
    int mid=(l+r)/2;
    if(pos<=mid)tr[x].ls=add(tr[x].ls,l,mid,pos);
    else tr[x].rs=add(tr[x].rs,mid+1,r,pos);
    tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;
    return x;
}
void dfs(int x){
    for(int v:e[x])
        dfs(v),rt[x]=merge(rt[x],rt[v],1,m);
    auto &now=ques[x];
    int pre=p[x].len,num=now.size();
    sort(now.rbegin(),now.rend());//按长度倒序 
    for(int i=0;i<num;i++){
        if(now[i+1].first==now[i].first)continue;
        pii op=now[i];
        int len=op.first,id=op.second;
        int ok=query(rt[x],1,m,k+1);//开始贡献答案的位置
        if(ok)
            ans[ok]+=pre-len,
            mx[ok]=max(mx[ok],pre);
        rt[x]=add(rt[x],1,m,id); 
        pre=len;
    }
    int ok=query(rt[x],1,m,k+1);
    if(ok)
        ans[ok]+=(x==0?1:pre-p[p[x].pre].len),
        mx[ok]=max(mx[ok],pre);
}
struct Q{
    int l,r,id;
}q[500005];
void work(){
    p[0].pre=-1;
    cin>>n>>m>>k;
    cin>>s;
    for(int i=0;i<n;i++)
        add(s[i]-'a'+1),pos[i+1]=lst;
    for(int i=1;i<=id;i++)
        fa[0][i]=p[i].pre,
        e[p[i].pre].push_back(i);
    for(int j=1;j<=19;j++)
        for(int i=1;i<=id;i++)
            fa[j][i]=fa[j-1][fa[j-1][i]];
    for(int i=1;i<=m;i++)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+1+m,[&](Q A,Q B){
        return A.l==B.l?(A.r==B.r?A.id<B.id:A.r<B.r):A.l<B.l;
    });
    for(int i=1;i<=m;i++){
        if(q[i].l==q[i-1].l&&q[i].r==q[i-1].r)continue;
        int l=q[i].l,r=q[i].r,op=pos[r];
        for(int j=19;j>=0;j--)
            if(fa[j][op]&&p[fa[j][op]].len>=r-l+1)
                op=fa[j][op];
        ques[op].push_back({r-l+1,q[i].id});
    }
    dfs(0);
    for(int i=1;i<=m;i++)
        ans[i]+=ans[i-1],mx[i]=max(mx[i],mx[i-1]),
        cout<<ans[i]<<' '<<mx[i]<<'\n';
}
int main(){
    //freopen("ansin.in","r",stdin);
    //freopen("ansout.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    work();
    return 0;
}

::::