【解题报告】SubString

前言

辛酸的调题过程：

前夜
20:30 -> 82pts 21:50 -> 0pts
当日
14:31 -> 27pts 14:52 -> 91pts 15:28 -> 100pts

题意

给你一个字符串，要求支持以下两个操作

1. 在当前字符串后面插入一个字符串 S
2. 查询字符串 S 在当前字符串中出现了几次

强制在线，$|S|\le6\times10^5,\quad Q\le10^4$

题解

如果没有强制在线，可以将所有插入字符串按顺序加入后，跑一遍 $SAM/SA$ ,对于每个询问划定区间查询即可

但如果强制在线呢？还是考虑 $SAM$ ，对于用 $SAM $建成的$parent$ 树来说，一个节点的子树和即为其答案

一般来说，$parent$ 树都是在我们跑完 $SAM$ 之后构建，我们考虑在 $SAM$ 插入字符的过程中进行构建，很显然我们只需要支持删边和加边的操作，可以用 $lct$ 简单维护

对于每个点的子树和，这其实一个链加的过程
即将 $x$ 连为 $y$ 的子树，直接将 $y->root(y)$ 全部加上 $si(x)$ 即可
$$
\large\color{grey}{\text{Talk is cheap , show you the code}}
$$

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1200005;
const int inf=0x3f3f3f3f;
int m,mask;
char s[maxn];

struct link_cut_tree
{
    int st[maxn];
    struct node
    {
        int ch[2],fa;
        int si,tag;
    }tr[maxn];
    inline bool pd(int x){return tr[tr[x].fa].ch[0]==x||tr[tr[x].fa].ch[1]==x;}
    inline void add(int x,int val){if(!x)return;tr[x].si+=val,tr[x].tag+=val;}
    inline void pushdown(int x){if(tr[x].tag){add(tr[x].ch[0],tr[x].tag),add(tr[x].ch[1],tr[x].tag),tr[x].tag=0;}}
    inline void rotate(int x)
    {
        int y=tr[x].fa,z=tr[y].fa,k=tr[y].ch[1]==x;
        if(pd(y))tr[z].ch[tr[z].ch[1]==y]=x;tr[y].ch[k]=tr[x].ch[k^1];tr[x].fa=z;
        if(tr[x].ch[k^1])tr[tr[x].ch[k^1]].fa=y;tr[x].ch[k^1]=y;tr[y].fa=x;
    }
    inline void splay(int x)
    {
        int y=x,z=0;while(y)st[++z]=y,y=tr[y].fa;while(z)pushdown(st[z--]);
        while(pd(x)){y=tr[x].fa,z=tr[y].fa;if(pd(y))rotate((tr[z].ch[1]==y)^(tr[y].ch[1]==x)?x:y);rotate(x);}
    }
    inline void access(int x){for(register int y=0;x;x=tr[y=x].fa)splay(x),tr[x].ch[1]=y;}
    inline void link(int x,int y){splay(x),tr[x].fa=y;access(y),splay(y),add(y,tr[x].si);}
    inline void cut(int x){access(x),splay(x),add(tr[x].ch[0],-tr[x].si),tr[tr[x].ch[0]].fa=0,tr[x].ch[0]=0;}
}supccz;

struct suffix_automaton
{
    int la=1,tot=1;
    struct node
    {
        int fa,len,ch[2];
    }tr[maxn];
    inline void insert(int x)
    {
        int p=la,u=++tot;supccz.tr[u].si=1;
        tr[u].len=tr[p].len+1;
        while(p&&!tr[p].ch[x])tr[p].ch[x]=u,p=tr[p].fa;
        if(!p)tr[u].fa=p|1,supccz.link(u,1);
        else
        {
            int q=tr[p].ch[x];
            if(tr[q].len==tr[p].len+1)tr[u].fa=q,supccz.link(u,q);
            else
            {
                int nu=++tot;tr[nu]=tr[q];
                supccz.cut(q),supccz.link(nu,tr[q].fa),supccz.link(u,nu),supccz.link(q,nu);    
                tr[nu].len=tr[p].len+1,tr[u].fa=tr[q].fa=nu;
                while(p&&tr[p].ch[x]==q)tr[p].ch[x]=nu,p=tr[p].fa;
            }
        }
        la=u;
    }
}ccz;
inline void decode(char *s,int mk,int len){for(register int i=0;i<len;++i){mk=(mk*131+i)%len,swap(s[i],s[mk]);}}
signed main(void)
{
    freopen("P5212.in","r",stdin);
    cin>>m;
    scanf("%s",s);
    int len=strlen(s);
    for(register int i=0;i<len;++i)ccz.insert(s[i]-'A');
    for(register int t,i=1;i<=m;++i)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            scanf("%s",s);
            int len=strlen(s);decode(s,mask,len);
            for(register int i=0;i<len;++i)ccz.insert(s[i]-'A');
        }
        else
        {
            scanf("%s",s);
            int len=strlen(s),u=1;decode(s,mask,len);
            for(register int j=0;j<len;++j)
            {
                u=ccz.tr[u].ch[s[j]-'A'];
                if(!u)break;
            }
            if(u)supccz.splay(u);
            t=supccz.tr[u].si;
            mask^=t;
            printf("%d\n",t);
        }
    }
    return 0;
}