bzoj 3879: SvT 접미사 로봇 + 접미사 트리 + 빈 트리

제목 대의: 문자열을 정하고 접두사 두 개 사이의 가장 긴 접두사와 접두사를 여러 번 물어본다.문제풀이: 먼저 접미사 나무를 간단하게 볼 수 있다. 그리고 접미사 자동기로 접미사 나무를 구축하면 누드나무 DP가 된다는 것을 자연스럽게 생각할 수 있다.정말 말하기 쉽네요. 쓸 때 몇 가지 문제를 주의해야 해요. 접미사를 대표하는 노드는 처음 삽입한 노드이고 중간에 nq가 보조 노드의 역할을 해요. 그리고, 별거 아닌 것 같아요. 쓰면 QAQ(이 카드는 QAQ)를 알 수 있어요.

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
namespace IStream
{
    char get_char()
    {
        static char *C,*mempool;
        const int L=1<<20;
        static char buffer[L];
        if(C==mempool)
            mempool=(C=buffer)+fread(buffer,1,L,stdin);
        if(C==mempool) return EOF;
        return *C++;
    }
    int get_int()
    {
        char c;
        do c=get_char();while((c<'0' || c>'9') && c!='-');
        int flag=1;
        if(c=='-') flag=-1;
        int re=0;
        while(c>='0' && c<='9')
        {
            re=(re<<1)+(re<<3)+c-'0';
            c=get_char();
        }
        return flag*re;
    }
}
struct sam
{
    int max_len,id;
    sam *son[26],*parent;
    sam(){}
}mempool[1000000],*root=&mempool[1],*last=root;
int now=1;
void Insert(int zm)
{
    sam *p=last;
    now++;
    sam *np=&mempool[now];
    mempool[now].id=now;
    np->max_len=p->max_len+1;
    while(p && !p->son[zm])
    {
        p->son[zm]=np;
        p=p->parent;
    }
    if(!p) np->parent=root;
    else
    {
        sam *q=p->son[zm];
        if(q->max_len==p->max_len+1) np->parent=q;
        else
        {
            now++;
            sam *nq=&mempool[now];
            mempool[now].id=now;
            nq->max_len=p->max_len+1;
            memcpy(nq->son,q->son,sizeof(nq->son));
            nq->parent=q->parent;
            q->parent=nq;
            np->parent=nq;
            while(p && p->son[zm]==q)
            {
                p->son[zm]=nq;
                p=p->parent;
            }
        }
    }
    last=np;
}
char s[1000000];
int pos[1000000];
long long siz[1000000];
struct bian
{
    int l,r;
}a[1000000];
int fir[1000000];
int timf[1000000];
int nex[1000000];
int pd[1000000];
int T;
int tot=1;
void add_edge(int l,int r)
{
    a[++tot].l=l;
    a[tot].r=r;
    if(timf[l]!=T)
    {
        fir[l]=0;
        timf[l]=T;
    }
    nex[tot]=fir[l];
    fir[l]=tot;
}
int fa[1000000][21];
int id[1000000];
int deep[1000000];
int cnt=0;
void dfs(int u,int fro)
{
    fa[u][0]=fro;
    id[u]=++cnt;
    deep[u]=deep[fro]+1;
    for(int o=fir[u];o;o=nex[o])
    {
        if(a[o].r==fro) continue;
        dfs(a[o].r,u);
    }
}
void init()
{
    for(int j=1;j<=19;j++)
        for(int i=1;i<=now;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
}
long long ans=0;
void dp(int u,int fro)
{
    siz[u]=(pd[u]==T?1:0);
    long long v=(u==1?0:mempool[u].max_len-mempool[fro].max_len);
    if(timf[u]!=T)
    {
        timf[u]=T;
        fir[u]=0;
    }
    for(int o=fir[u];o;o=nex[o])
    {
        dp(a[o].r,u);
        siz[u]+=siz[a[o].r];
    }
    ans+=v*siz[u]*(siz[u]-1)/2;
}
int get_lca(int x,int y)
{
    if(deep[x]for(int i=19;i>=0;i--) if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int aa[4000000];
bool cmp(int a,int b)
{
    return id[a]int my_stack[4000000];
int main()
{
    mempool[1].id=1;
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    using namespace IStream;
    for(int i=n;i>=1;i--)
    {
        Insert(s[i]-'a');
        pos[i]=last->id;
    }
    for(int i=2;i<=now;i++)
        add_edge(mempool[i].parent->id,mempool[i].id);
    dfs(1,0);
    init();
    for(int hh=1;hh<=m;hh++)
    {
        T++;
        ans=0;
        tot=1;
        int nn;
        nn=get_int();
        for(int i=1;i<=nn;i++)
        {
            aa[i]=get_int();
            aa[i]=pos[aa[i]];
            pd[aa[i]]=T;
        }
        sort(aa+1,aa+1+nn,cmp);
        int top=1;
        my_stack[top]=1;
        for(int i=1;i<=nn;i++)
        {
            if(aa[i]==aa[i-1]) continue;
            int lca=get_lca(aa[i],my_stack[top]);
            while(1)
            {
                if(top>1 && deep[lca]1]])
                {
                    add_edge(my_stack[top-1],my_stack[top]);
                    top--;
                }
                else if(deep[lca]break;
                }
                else break;
            }
            if(my_stack[top]!=lca) my_stack[++top]=lca;
            my_stack[++top]=aa[i];
        }
        while(top>1)
        {
            add_edge(my_stack[top-1],my_stack[top]);
            top--;
        }
        dp(1,0);
        printf("%lld
",ans);
    }
    return 0;
}