BZOJ-2555: SubString

Description

懒得写背景了，给你一个字符串init，要求你支持两个操作
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
你必须在线支持这些操作。长度 <= 600000，询问次数<= 10000,询问总长度<= 3*10^6

后缀自动机+splay维护pre树dfs序上的区间和。出现次数即为right集合大小，即为pre树上子树中结束节点的个数，用splay动态维护即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 601000
struct node
{
    node *c[2],*fa;
    int s,w;
    node(int x);
    void pushup();
}*null=new node(0),*in[N<<1],*out[N<<1],*root;
node::node(int x)
{
    c[0]=c[1]=fa=null;
    s=w=x;
}
void node::pushup() {s=c[0]->s+c[1]->s+w;}
void rotate(node *x)
{
    node *y=x->fa; int l=(x==y->c[1]),r=l^1;
    y->c[l]=x->c[r]; x->c[r]->fa=y;
    x->c[r]=y; x->fa=y->fa;
    y->fa->c[y==y->fa->c[1]]=x;
    y->fa=x; y->pushup(); x->pushup();
    if(root==y) root=x;
}
void splay(node *x,node *tar)
{
    node *y,*z;
    while(x->fa!=tar)
    {
        y=x->fa; z=y->fa;
        if(z!=tar) rotate(((y==z->c[0])^(x==y->c[0])) ? x : y);
        rotate(x);
    }
}
void initialize()
{
    in[1]=root=new node(0);
    out[1]=root->c[1]=new node(0);
    root->c[1]->fa=root;
    root->pushup();
}
node *bef(node *x)
{
    node *re=x->c[0];
    while(re->c[1]!=null) re=re->c[1];
    return re;
}
node *aft(node *x)
{
    node *re=x->c[1];
    while(re->c[0]!=null) re=re->c[0];
    return re;
}
int ch[N<<1][26],pre[N<<1],dep[N<<1],tot=1,last=1;
void insert(int x)
{
    int p=last,cur=++tot; last=cur; dep[cur]=dep[p]+1;
    for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;

    in[cur]=new node(1);
    out[cur]=new node(0);
    in[cur]->c[1]=out[cur];
    out[cur]->fa=in[cur];

    if(!p) pre[cur]=1,splay(in[1],null),splay(aft(in[1]),root);
    else
    {
        int q=ch[p][x];
        if(dep[q]==dep[p]+1) pre[cur]=q,splay(in[q],null),splay(aft(in[q]),root);
        else
        {
            int clo=++tot;
            in[clo]=new node(0); out[clo]=new node(0);

            splay(in[q],null);
            splay(bef(in[q]),null);
            splay(in[q],root);
            root->c[1]->c[0]=in[clo];
            in[clo]->fa=root->c[1];
            root->c[1]->pushup(); root->pushup();

            splay(out[q],null);
            splay(aft(out[q]),root);
            root->c[1]->c[0]=out[clo];
            out[clo]->fa=root->c[1];
            root->c[1]->pushup(); root->pushup();

            memcpy(ch[clo],ch[q],sizeof ch[q]);
            dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
            for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
            splay(in[clo],null);
            splay(aft(in[clo]),root);
        }
    }
    root->c[1]->c[0]=in[cur];
    in[cur]->fa=root->c[1];
    root->c[1]->pushup();
    root->pushup();
}
int query(int x)
{
    splay(in[x],null);
    splay(out[x],root);
    return in[x]->w+root->c[1]->c[0]->s;
}
char st[3001000];
int mark;
void decode(int len,int x)
{
    for(int i=0;i<len;++i)
        swap(st[i],st[x=(x*131+i)%len]);
}
int main()
{
    int T; scanf("%d%s",&T,st);
    int len=strlen(st);
    initialize();
    for(int i=0;i<len;++i) insert(st[i]-'A');
    char sw[10]; int i,p,ans;
    while(T--)
    {
        scanf("%s%s",sw,st);
        len=strlen(st); decode(len,mark);
        if(sw[0]=='A') for(i=0;i<len;++i) insert(st[i]-'A');
        else
        {
            for(p=1,i=0;p&&i<len;++i) p=ch[p][st[i]-'A'];
            ans= p ? query(p) : 0;
            mark^=ans;
            printf("%d\n",ans);
        }
    }
    return 0;
}