题目大意:给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

首先离线,然后构出后缀树。

先把每个前缀都打上标记,并记上他的出现时间。

对于一个点,他的贡献就是l[i]-l[fa[i]],贡献时间就是以他为根的子树中出现时间第K小的前缀的出现时间。

这个可以用主席树在dfs序上求第k大,也可以用左偏树维护sz<=k的大根堆。

我用的左偏树。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 200000 + 50000 + 9;
char s[N];
struct node
{
    int l,r,dis,sz,v;
    node(){}
    node(const int _l,const int _r,const int _dis,const int _sz,const int _v):
        l(_l),r(_r),dis(_dis),sz(_sz),v(_v){}
}t[N * 2];
int son[N * 2],lnk[N * 3],nxt[N * 3],ec;
int n,m,k,Time[N * 2],rt[N * 2],nodes,tcnt;
long long ans[N];
int last,cnt,ch[N * 2][26],fa[N * 2],l[N * 2],len;
inline void addedge(int x,int y)
{
    nxt[++ec] = son[x];
    lnk[son[x] = ec] = y;
}
void add(int c)
{
    int np = ++cnt,p = last; last = np;
    l[np] = ++len; Time[np] = tcnt;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np; memset(ch[np],0,sizeof ch[np]);
    if (!p) fa[np] = 1;
    else {
        int q = ch[p][c];
        if (l[p] + 1 == l[q]) fa[np] = q;
        else {
            int nq = ++cnt;
            Time[nq] = -1;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            fa[nq] = fa[q];
            l[nq] = l[p] + 1;
            fa[q] = fa[np] = nq;
            for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
        }
    }
}
int merge(int a,int b)
{
    //++d;
    //if (d > 1000) printf("%d\n",d);
    if (!a || !b) return a + b;
    if (t[a].v < t[b].v) std::swap(a,b);
    t[a].r = merge(t[a].r,b);
    if (t[t[a].r].dis > t[t[a].l].dis) std::swap(t[a].l,t[a].r);
    t[a].dis = t[t[a].r].dis + 1;
    t[a].sz = t[t[a].r].sz + t[t[a].l].sz + 1;
    //--d;
    return a;
}
void dfs(int u)
{
    for (int i = son[u]; i; i = nxt[i]) {
        dfs(lnk[i]);
        rt[u] = merge(rt[u],rt[lnk[i]]);
        while (t[rt[u]].sz > k) rt[u] = merge(t[rt[u]].l,t[rt[u]].r);
    }
    if (Time[u] != -1) {
        t[++nodes] = node(0,0,1,1,Time[u]);
        rt[u] = merge(nodes,rt[u]);
    }
    while (t[rt[u]].sz > k) rt[u] = merge(t[rt[u]].l,t[rt[u]].r);
    if (t[rt[u]].sz == k) ans[t[rt[u]].v] += l[u] - l[fa[u]];
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("k-string.in","r",stdin);
    freopen("k-string.out","w",stdout);
    #endif
    while (~scanf("%d%d%d\n",&n,&m,&k)) {
        memset(ch[1],0,sizeof ch[1]);
        scanf("%s\n",s);
        tcnt = 0;
        cnt = last = 1; len = 0;
        for (char *c = s; *c; ++c) add(*c - 'a');
        while (m--) {
            int t;
            scanf("%d",&t);
            if (t == 1) {
                char tc,c;
                scanf("%c%c",&tc,&c);
                add(c - 'a');
                Time[last] = tcnt;
            }else ans[tcnt++] = 0;
        }
        nodes = ec = 0;
        for (int i = 1; i <= cnt; ++i) rt[i] = son[i] = 0;
        for (int i = 2; i <= cnt; ++i) addedge(fa[i],i);
        dfs(1);
        long long as = 0;
        for (int i = 0; i < tcnt; ++i) {
            as += ans[i];
            printf("%I64d\n",as);
        }
    }
}

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project