Codeforces 204E Little Elephant and Strings

草，调了一年发现我把串的个数当总串长写了……
我寻思我写 CF666E 的时候就注意到这个问题了呀（

线段树合并求出每个状态在多少个字符串里出现了，并标记有哪些状态是出现至少 k 次的。
那么对于每个串，从每个前缀往上跳 Parent Tree 计算符合条件的子串的个数即可。

然而暴力跳复杂度显然很危险（
然而实际上可以直接从根向下 DP 预处理出个数（
然而实际上只需要向上找一个最深的符合条件的状态即可，因为符合条件在树链上显然有单调性（

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,k;
char s[N + 5];
int ed[N + 5],pos[N + 5],tot;
long long ans[N + 5];
namespace SEG
{
    struct node
    {
        int sum;
        int ls,rs;
    } seg[(N << 5) + 10];
    int tot;
    void insert(int x,int &p,int tl,int tr)
    {
        !p && (p = ++tot);
        if(tl == tr)
        {
            seg[p].sum |= 1;
            return ;
        }
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
        seg[p].sum = seg[seg[p].ls].sum + seg[seg[p].rs].sum;
    }
    int merge(int p,int q,int tl,int tr)
    {
        if(!p || !q)
            return p | q;
        if(tl == tr)
        {
            seg[p].sum |= seg[q].sum;
            return p;
        }
        int mid = tl + tr >> 1;
        seg[p].ls = merge(seg[p].ls,seg[q].ls,tl,mid),seg[p].rs = merge(seg[p].rs,seg[q].rs,mid + 1,tr);
        seg[p].sum = seg[seg[p].ls].sum + seg[seg[p].rs].sum;
        return p;
    }
}
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len,rt;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    int vis[(N << 1) + 5],f[(N << 1) + 5];
    inline void insert(int x,int pos)
    {
        if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
        {
            SEG::insert(pos,sam[las = sam[las].ch[x]].rt,1,n);
            return ;
        }
        int cur = las,p = ++tot,flag = 0,nxt;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                cur == las && (flag = 1),nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].rt = 0;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        SEG::insert(pos,sam[las = flag ? nxt : p].rt,1,n);
    }
    inline void build()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= N;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            SEG::seg[sam[a[i]].rt].sum >= k && (vis[a[i]] = 1),sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt,1,n);
        for(register int i = 2;i <= tot;++i)
            f[a[i]] = vis[a[i]] ? sam[a[i]].len : f[sam[a[i]].fa];
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(register int i = 1;i <= n;++i)
    {
        scanf("%s",s),SAM::las = 1;
        for(char *c = s;*c;SAM::insert(*c++ - 'a',i),ed[++tot] = SAM::las,pos[tot] = i);
    }
    SAM::build();
    for(register int i = 1;i <= tot;++i)
        ans[pos[i]] += SAM::f[ed[i]];
    for(register int i = 1;i <= n;++i)
        printf("%lld%c",ans[i]," \n"[i == n]);
}