hdu4641 sam 左偏树

hdu4641.cpp

#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);
        }
    }
}