题解：P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2

先考虑如何对一个三元组 (l,r,k) 进行判断：

从左向右考虑，每次从目前已经包括的区域贪心地选取尽可能后的串。之后和 k 比较即可（可以塞空串）。

显然可以固定左端点，贪心对每个 (l,r) 求得最小的 k 满足条件。并且可知当 l 一定，最小的 k 具有单调性。

发现对贪心取得的序列贪心拓展是简单的。考虑每次把扩展的答案进行计数。

一段区间 l=L,r\in [L,R) 在 k 固定时，对总答案的贡献为 R-L，对 ans_i,i\in [L,R) 的贡献为 R-i。可以通过二阶差分进行计算，时间复杂度 O(nk)。

考虑我们如何计算这个二阶差分：对 \Delta^2_l ，\Delta^2 _{l+1}，\Delta^2_{r+1} 分别存在赋值。 第一项加上 R-L，第二项减去 R-L+1，第三项加上 1。

先处理第一项：其为 \sum (R -L)=\sum R-k L。

考虑每次贪心扩展的过程：找到最大的扩展区域，并在新扩展区域找到下一步可能最大的扩展区域。

“找到最大”可以 ST 表。以上过程可以倍增：跳 2^k 步骤的位置和 \sum R。

第二项类似。现在考虑第三项：再次考虑跳的过程：其相当于有一些起点，每次往一个位置赋值并且跳，每个点都跳 k 步。

可能在某一步骤开始不动。考虑跳 k 步后的终点，其可能被作为保持不动的点进行若干轮次。于是处理出第一次到终点的步骤数，起点 +1，终点 -1，终点之后的打转先算，剩下的从左向右扫即可。

#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
#define int long long
string s[500005],t;
int sl[500005];
unsigned long long bas[500005],tb[500005];
const int base=41;
vector<int>nex[500005];
int maxr[500005];
int st[20][500005];
int stp[20][500005];
int gemax(int l,int r){
    int le=r-l+1,p=__lg(le);
    return max(st[p][l],st[p][r-(1ll<<p)+1]);
}
int gemaxpos(int l,int r){
    int le=r-l+1,p=__lg(le);
    if(gemax(l,r)==st[p][r-(1ll<<p)+1])return stp[p][r-(1ll<<p)+1];
    else return stp[p][l];
}
int pans,ans[500005],dans[500005],ddans[500005];
int nec[500005][21],suc[500005][21];
int pk[500005];
//int nec[500005][20];
signed main(){
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    bas[0]=1;
    for(int i=1;i<=500001;i++)bas[i]=bas[i-1]*base;
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int id,n,k;
    cin>>id>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        sl[i]=s[i].length();
        s[i]='&'+s[i]+'&';
    }
    cin>>t;
    int m=t.length();
    t='$'+t+'$';
    for(int i=1;i<=m;i++){
        maxr[i]=i;
        tb[i]=tb[i-1]*base+t[i]-'a'+1;
    }
    for(int i=1;i<=n;i++){
        nex[i].resize(s[i].size());
        nex[i][0]=0;
        for(int j=1;j<=sl[i];j++){
            nex[i][j]=nex[i][j-1]*base+s[i][j]-'a'+1;
        }
        for(int j=1;j<=m;j++){
            int l=0,r=sl[i]+1;
            while(l+1<r){
                int mid=(l+r)>>1;
                if(j+mid-1<=m&&nex[i][mid]==tb[j+mid-1]-tb[j-1]*bas[mid])l=mid;
                else r=mid;
            }
            maxr[j]=max(maxr[j],j+l);
//          cout<<l<<' '<<r<<endl;
        }
    }
    maxr[m+1]=m+1;
    for(int i=1;i<=m+1;i++){
        st[0][i]=maxr[i];
        stp[0][i]=i;
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1ll<<j)-1<=m+1;i++){
            st[j][i]=max(st[j-1][i],st[j-1][i+(1ll<<(j-1))]);
            if(st[j-1][i]>st[j-1][i+(1ll<<(j-1))])stp[j][i]=stp[j-1][i];
            else stp[j][i]=stp[j-1][i+(1ll<<(j-1))];
        }
    }
    nec[m+1][0]=m+1;
    suc[m+1][0]=m+1;
    for(int i=1;i<=m;i++){
        nec[i][0]=gemaxpos(i,maxr[i]);
        suc[i][0]=maxr[i];
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=m+1;i++){

            nec[i][j]=nec[nec[i][j-1]][j-1];
            suc[i][j]=suc[i][j-1]+suc[nec[i][j-1]][j-1];
//          cout<<i<<' '<<j<<' '<<nec[i][j]<<' '<<suc[i][j]<<endl;
        }
    }
    for(int l=1;l<=m;l++){
        int r=l;
        int su=0;int kk=k;
//      cout<<l<<' '<<kk<<endl;
        for(int j=20;j>=0;j--){
            while(kk>=1ll<<j){
//              cout<<r<<' '<<j<<' '<<' '<<suc[r][j]<<endl;
                su+=suc[r][j];
                r=nec[r][j];
                kk-=1ll<<j;
            }
        }
//      cout<<r<<endl;
        pans+=su-l*k;
        ddans[l]+=su-l*k;
        ddans[l+1]-=su-l*k+k;
        pk[l]++;
        int p=r;r=l;
        int ste=0;
        for(int i=20;i>=0;i--){
            while((ste+(1ll<<i))<=k&&nec[r][i]!=p){
                ste+=1ll<<i;
                r=nec[r][i];
            }
        }
        if(r!=p)ste++;
        pk[p]--;
//      cout<<l<<' '<<r<<' '<<p<<endl;
        ddans[maxr[p]+1]+=k-ste;

    }
//  for(int i=1;i<=m;i++){
//      cout<<pk[i]<<' ';
//  }
    for(int i=1;i<=m;i++){
        ddans[maxr[i]+1]+=pk[i];
        pk[nec[i][0]]+=pk[i];
    }
    cout<<pans<<'\n';
    for(int i=1;i<=m;i++){
//      cout<<ddans[i]<<' ';
        dans[i]=dans[i-1]+ddans[i];
        ans[i]=ans[i-1]+dans[i];
        cout<<ans[i]<<' ';
    }
    return 0;
}
}
bool en;
signed main(){
    #ifdef LOCAL_WRK
    cerr<<"[Static Memory : "<<fixed<<((&st)-(&en))/1048576.0<<"MB]"<<endl;
    #endif
       return _wrk::main();
}

AC 记录。