bzoj 2555 SubString

Description

懒得写背景了，给你一个字符串init，要求你支持两个操作

(1):在当前字符串的后面插入一个字符串

(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)

你必须在线支持这些操作。

Input

第一行一个数Q表示操作个数

第二行一个字符串表示初始字符串init

接下来Q行，每行2个字符串Type,Str

Type是ADD的话表示在后面插入字符串。

Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量mask，初始值为0

读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。

询问的时候，对TrueStr询问后输出一行答案Result

然后mask = mask xor Result

插入的时候，将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压

Output

Sample Input

2
A
QUERY B
ADD BBABBBBAAB

Sample Output

0

HINT

40 % 的数据字符串最终长度 <= 20000，询问次数<= 1000，询问总长度<=10000

100 % 的数据字符串最终长度 <= 600000，询问次数<= 10000,询问总长度<=3000000

新加数据一组–2015.05.20

题解

加入新节点后，它的祖先的right集合都要加1

因为加入节点的时候Parent树的形态会改变，那就再套个数据结构。。动态树肯定是LCT比较好。。

但是网上说暴力比LCT快4倍= =

还有就是我调了一下午是因为读入的decode写错了。。。。注意mask用的时候不能直接用，要提出来个值。。

#include <cstdio>
#include <cstring>
#define N 1200010
using namespace std;
struct lcts
{
    int f[N],ch[N][2],val[N],add[N];
    void add_tag(int x,int v){val[x]+=v,add[x]+=v;}
    void pushdown(int x)
    {
        if (add[x])
        {
            if (ch[x][0]) add_tag(ch[x][0],add[x]);
            if (ch[x][1]) add_tag(ch[x][1],add[x]);
            add[x]=0;
        }
    }
    int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}
    int get_son(int x){return ch[f[x]][1]==x;}
    void rot(int x)
    {
        int fa=f[x],fafa=f[fa],k=get_son(x);
        if (!is_root(fa))
            ch[fafa][ch[fafa][1]==fa]=x;
        ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa;
        ch[x][k^1]=fa,f[fa]=x;
        f[x]=fafa;
    }
    void push(int x)
    {
        if(!is_root(x)) push(f[x]);
        pushdown(x);
    }
    void splay(int x)
    {
        push(x);
        for (int fa;!is_root(x);rot(x))
            if (!is_root(fa=f[x]))
                rot(get_son(x)==get_son(fa)?fa:x);
    }
    void access(int x)
    {
        for (int y=0;x;y=x,x=f[x])
            splay(x),ch[x][1]=y/*,update(x)*/;
    }
    void link(int x,int y){f[x]=y,access(y),splay(y),add_tag(y,val[x]);}
    void cut(int x){access(x),splay(x),add_tag(ch[x][0],-val[x]),ch[x][0]=f[ch[x][0]]=0;}
}T;
char s[N],com[100];
int dis[N],fa[N],ch[N][26],sz=1,root=1,last=root,len;
void link(int x,int y){fa[x]=y,T.link(x,y);}
void insert(int x)
{
    int now=++sz,pre=last;last=now;
    T.val[now]=1;dis[now]=dis[pre]+1;
    for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
    if (!pre) link(now,root);
    else if (dis[pre]==dis[ch[pre][x]]+1) link(now,ch[pre][x]);
    else
    {
        int q=ch[pre][x],nows=++sz;dis[nows]=dis[pre]+1;
        memcpy(ch[nows],ch[q],sizeof ch[nows]);
        link(nows,fa[q]),T.cut(q),link(q,nows),link(now,nows);
        for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
    }
}
int query(char s[])
{
    int le=strlen(s),now=root;
    for (int i=0;i<le;i++)
        if (!ch[now][s[i]-'A'])
            return 0;
        else now=ch[now][s[i]-'A'];
    T.splay(now);
    return T.val[now];
}
main()
{
    int T,mask=0,las=0;
    scanf("%d",&T);
    scanf("%s",s+1);
    len=strlen(s+1);
    for (int i=1;i<=len;i++)
        insert(s[i]-'A');
    while(T--)
    {
        scanf("%s%s",com,s);
        len=strlen(s);
        int te=mask;
        for (int i=0;i<len;i++)
        {
            te=(te*131+i)%len;
            char t=s[i];s[i]=s[te],s[te]=t;
        }
        if (com[0]=='A')
            for (int i=0;i<len;i++)
                insert(s[i]-'A');
        else
            las=query(s),printf("%d\n",las),mask^=las;
//      printf("%d\n",mask);
    }
}