【BZOJ-2555】SubString 后缀自动机 + LinkCutTree

时间：2021-08-31 00:05:42

2555: SubString

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 1936  Solved: 551
[Submit][Status][Discuss]

Description

懒得写背景了，给你一个字符串init，要求你支持两个操作
    (1):在当前字符串的后面插入一个字符串
    (2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
    你必须在线支持这些操作。

Input

第一行一个数Q表示操作个数
    第二行一个字符串表示初始字符串init
    接下来Q行，每行2个字符串Type,Str 
    Type是ADD的话表示在后面插入字符串。
    Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
    为了体现在线操作，你需要维护一个变量mask，初始值为0
【BZOJ-2555】SubString 后缀自动机 + LinkCutTree    
    读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。
    询问的时候，对TrueStr询问后输出一行答案Result
    然后mask = mask xor Result  
    插入的时候，将TrueStr插到当前字符串后面即可。

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

Output

Sample Input

2
A
QUERY B
ADD BBABBBBAAB

Sample Output

HINT

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

新加数据一组--2015.05.20

Source

Ctsc模拟赛By 洁妹

Solution

论文里最难搞的一道题，谢谢 abclzr队长 的帮助。

一个串在模板串中的出现次数显然就是$|Right(s)|$，然后这个的求法是$Parent$树的子树中的叶子节点个数。

暴力的查询是单次$O(N)$，总体$O(N^{2})$的，所以要利用数据结构LCT维护，实现查询$O(logN)$。

在构建SAM的同时要在LCT上进行相应的Link/Cut操作，在Cut的时候，需要将其贡献减去。

样例有点弱，自己搞了个测试点：

ABABA

QUERY AB

QUERY A

ADD BAB

QUERY AB

QUERY A

Input





Output




Code




#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define MAXN 1200010

char S[MAXN];

int N,Q,M,ans,Mask;

inline void read()

{

    string str=S+1;

    int mask=Mask;

    for (int i=0; i<str.length(); i++)

        {

            mask=(mask*131+i)%str.length();

            swap(str[i],str[mask]);

        }

    for (int i=0,tot=0; i<str.length(); i++) S[++tot]=str[i];

}

namespace LCT

{

    int fa[MAXN],ch[MAXN][2],val[MAXN],tag[MAXN];

    inline bool is_root(int x) {return !fa[x] || ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;}

    inline void Add(int x,int v) {if (!x) return; val[x]+=v,tag[x]+=v;}

    inline void Pushdown(int x) {if (tag[x]) Add(ch[x][0],tag[x]),Add(ch[x][1],tag[x]),tag[x]=0;}

    inline void Rotate(int x)

    {

        int y=fa[x],w=ch[y][1]==x,z=fa[y];

        ch[y][w]=ch[x][w^1];

        if (ch[x][w^1]) fa[ch[x][w^1]]=y;

        if (ch[z][0]==y) ch[z][0]=x; else if (ch[z][1]==y) ch[z][1]=x;

        fa[x]=fa[y]; fa[y]=x; ch[x][w^1]=y;

    }

    int stack[MAXN];

    inline void Splay(int x)

    {

        int top=0,t=x,y; stack[++top]=x;

        while (!is_root(t)) stack[++top]=t=fa[t];

        while (top) Pushdown(stack[top--]);

        while (!is_root(x))

            {

                y=fa[x];

                if (!is_root(y))

                    if ((ch[fa[y]][0]==y)^(ch[y][0]==x)) Rotate(x);

                        else Rotate(y);

                Rotate(x);

            }

    }

    inline void Access(int x) {for (int y=0; x; y=x,x=fa[x]) Splay(x),ch[x][1]=y;}

    inline void Link(int x,int y) {fa[x]=y; Access(y); Splay(y); Add(y,val[x]);}

    inline void Cut(int x) {Access(x); Splay(x); Add(ch[x][0],-val[x]); fa[ch[x][0]]=0,ch[x][0]=0;}

}using namespace LCT;

namespace SAM

{

    int son[MAXN][27],len[MAXN],par[MAXN];

    int root,last,sz;

    inline void Init() {root=last=sz=1;}

    inline void Extend(int c)

    {

        int cur=++sz,p=last;

        len[cur]=len[p]+1; LCT::val[cur]=1;

        while (p && !son[p][c]) son[p][c]=cur,p=par[p];

        if (!p) par[cur]=root,LCT::Link(cur,root);

        else

            {

                int q=son[p][c];

                if (len[p]+1==len[q]) par[cur]=q,LCT::Link(cur,q);

                else

                    {

                        int nq=++sz;

                        memcpy(son[nq],son[q],sizeof(son[nq]));

                        len[nq]=len[p]+1,par[nq]=par[q]; LCT::Link(nq,par[nq]);

                        while (p && son[p][c]==q) son[p][c]=nq,p=par[p];

                        par[cur]=par[q]=nq;

                        LCT::Cut(q); LCT::Link(cur,nq); LCT::Link(q,nq);

                    }

            }

        last=cur;

    }

    inline void Build() {Init(); for (int i=1; i<=N; i++) Extend(S[i]-'A'+1);}

    inline void Insert()

    {

        read(); M=strlen(S+1);

        for (int i=1; i<=M; i++) Extend(S[i]-'A'+1);

    }

    inline int Query()

    {

        read(); M=strlen(S+1);

        int now=root;

        for (int i=1; i<=M; i++)

            if (!son[now][S[i]-'A'+1]) return 0;

                else now=son[now][S[i]-'A'+1];

        LCT::Splay(now);

        return val[now];

    }

}using namespace SAM;

int main()

{

    scanf("%d",&Q);

    scanf("%s",S+1); N=strlen(S+1);

    SAM::Build();

    while (Q--)

        {

            char opt[10];

            scanf("%s%s",opt+1,S+1);

            switch (opt[1])

                {

                    case 'A' : SAM::Insert(); break;

                    case 'Q' : printf("%d\n",ans=SAM::Query()); Mask^=ans; break;

                }

//            for (int i=1; i<=sz; i++) printf("%d %d %d %d\n",i,ch[i][0],ch[i][1],val[i]);

        }

    return 0;

}





　　


太久没看LCT了，出现大片遗忘，背了个模板都能弄错，其实应该先复习一下LCT再写这道题的。


相关文章