P11401 题解

dAniel_lele · 2025-01-28 23:28:01 · 题解

建出 SA，枚举长度 x。

对于每个子串的等价类维护一个 a_i 递增集合。

如果 SA 之后相邻两个后缀的 lcp 为 x，即对于所有长度小于等于 x 的子串这两个位置开始的均相同，那么需要合并并修改递增集合。

考虑启发式合并，每次加入先判断是否是前缀最大值，然后将后面的小于他的 erase。注意别让你的指针失效了，有一位 APIO 斩获 115 分的选手在 WC 考场上因为这件事挂分痛失 AK。

总复杂度 O(n\log^2n)。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
set<pair<int,int>> st[100005];
int fd[100005];
int find(int i){
    return fd[i]==i?fd[i]:fd[i]=find(fd[i]);
}
string s; int n,a[100005];
int f[100005][20],len,ord[100005],rpos[100005],reml[100005];
vector<pair<int,int>> v1[100005],v2[100005];
int lcp(int i,int j){
    int ret=0;
    for(int k=19;k>=0;k--){
        if(i>=(1<<k)&&j>=(1<<k)){
            if(f[i][k]==f[j][k]){
                ret+=(1<<k);
                i-=(1<<k);
                j-=(1<<k);
            }
        }
    }
    return ret;
}
int ans[100005];
signed main(){
    cin>>s; n=s.size(); s=" "+s;
    for(int i=1;i<=n;i++) cin>>a[i],fd[i]=i;
    for(int i=1;i<=n;i++) f[i][0]=s[i]-'a'+1; len=26;
    for(int i=1;i<=19;i++){
        for(int j=0;j<=max(len,n);j++) v1[j].clear(),v2[j].clear();
        for(int j=1;j<=n;j++) if(j<=(1<<(i-1))) v1[0].push_back(make_pair(f[j][i-1],j)); else v1[f[j-(1<<(i-1))][i-1]].push_back(make_pair(f[j][i-1],j));
        for(int j=0;j<=max(len,n);j++) for(auto v:v1[j]) v2[v.first].push_back(make_pair(j,v.second));
        int cnt=0; pair<int,int> lst=make_pair(-1,-1);
        for(int j=0;j<=max(len,n);j++) for(auto v:v2[j]) cnt+=(make_pair(j,v.first)!=lst),lst=make_pair(j,v.first),f[v.second][i]=cnt;
    }
    for(int i=1;i<=n;i++) ord[i]=f[i][19],rpos[ord[i]]=i;
    vector<pair<int,int>> tmp;
    for(int i=1;i<n;i++) reml[i]=lcp(rpos[i],rpos[i+1]),tmp.push_back(make_pair(reml[i],i));
    sort(tmp.begin(),tmp.end()); reverse(tmp.begin(),tmp.end());
    int it=0,ret=0;
    for(int i=n;i>=1;i--){
        st[i].insert(make_pair(i,a[i])); ret++;
        while(it!=tmp.size()&&tmp[it].first==i){
//          cout<<i<<" "<<tmp[it].first<<" "<<tmp[it].second<<"\n";
            int pos=tmp[it].second;
            int u=find(rpos[pos]),v=find(rpos[pos+1]);
            if(st[u].size()<st[v].size()) swap(u,v);
            ret-=st[u].size(),ret-=st[v].size();
            for(auto p:st[v]){
                vector<pair<int,int>> remdel;
                auto now=st[u].lower_bound(p);
                if(now!=st[u].begin()&&((*prev(now)).second>=p.second)) continue;
                while(now!=st[u].end()&&(p.second>=(*now).second)){
                    remdel.push_back(*now);
                    now=next(now);
                }
                for(auto q:remdel) st[u].erase(st[u].find(q));
                st[u].insert(p);
            }
            ret+=st[u].size();
            fd[v]=u;
            it++;
        }
        ans[i]=ret;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}