bzoj 2555 SubString —— 后缀自动机+LCT

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2555

建立后缀自动机，就可以直接加入新串了；

出现次数就是 Right 集合的大小，需要查询 Parent 树上的子树和；

所以可以用 LCT 维护 Parent 树，因为 Parent 树是有根树所以不需要 makeroot；

代码中的两种 cut 写法都可以，其实这里的 splay 节点上记的 siz 值不是 splay 子树里的而是原子树( Parent 树上)里的；

注意读入的函数内不改变 mask -_-

splay 用栈时不要改变 x ！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const xn=,xm=3e6+;

int fa[xn],lst=,cnt=,l[xn],go[xn][],siz[xn];

int pre[xn],c[xn][],sta[xn],top,lzy[xn],mask;

char dc[],s[xm];

void turn(int x,int w){siz[x]+=w; lzy[x]+=w;}//

bool isroot(int x){return c[pre[x]][]!=x&&c[pre[x]][]!=x;}

void pushdown(int x)

{

  if(!lzy[x])return;

  int ls=c[x][],rs=c[x][];

  turn(ls,lzy[x]); turn(rs,lzy[x]);

  lzy[x]=;

}

void rotate(int x)

{

  int y=pre[x],z=pre[y],d=(c[y][]==x);

  if(!isroot(y))c[z][c[z][]==y]=x;

  pre[x]=z; pre[y]=x; pre[c[x][!d]]=y;

  c[y][d]=c[x][!d]; c[x][!d]=y;

}

void splay(int x)

{

  sta[top=]=x;

  //while(!isroot(x))sta[++top]=pre[x],x=pre[x];//don't change x!!

  for(int i=x;!isroot(i);i=pre[i])sta[++top]=pre[i];

  while(top)pushdown(sta[top--]);

  while(!isroot(x))

    {

      int y=pre[x],z=pre[y];

      if(!isroot(y))

    {

      if((c[y][]==x)^(c[z][]==y))rotate(x);

      else rotate(y);

    }

      rotate(x);

    }

}

void access(int x)

{

  for(int t=;x;c[x][]=t,t=x,x=pre[x])splay(x);

}

void link(int x,int f)

{

  pre[x]=f; access(f); splay(f); turn(f,siz[x]);//line to root

}

void Cut(int x)

{

  access(x); splay(x); turn(c[x][],-siz[x]); pre[c[x][]]=; c[x][]=;//c[x][0]:parent

}

void cut(int x)//

{

  access(x); int y=fa[x]; splay(y);//

  turn(y,-siz[x]); fa[x]=; c[y][]=;

}

void add(int w)

{

  int p=lst,np=++cnt; lst=np; l[np]=l[p]+; siz[np]=;

  for(;p&&!go[p][w];p=fa[p])go[p][w]=np;

  if(!p)fa[np]=,link(np,);

  else

    {

      int q=go[p][w];

      if(l[q]==l[p]+)fa[np]=q,link(np,q);

      else

    {

      int nq=++cnt; l[nq]=l[p]+;

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

      fa[nq]=fa[q]; link(nq,fa[q]);

      fa[np]=nq; link(np,nq);

      cut(q); fa[q]=nq; link(q,nq);

      for(;go[p][w]==q;p=fa[p])go[p][w]=nq;

    }

    }

}

int query(int l)

{

  int p=;//

  for(int i=;i<l;i++)

    {

      if(!go[p][s[i]-'A'])return ;

      p=go[p][s[i]-'A'];

    }

  access(p); splay(p); return siz[p];//

}

int main()

{

  int Q; scanf("%d",&Q);

  scanf("%s",s+); int l=strlen(s+);

  for(int i=;i<=l;i++)add(s[i]-'A');

  for(int i=;i<=Q;i++)

    {

      scanf("%s",dc); scanf("%s",s); l=strlen(s);

      int tmp=mask;//!!-_-

      for(int j=;j<l;j++)

    {

      tmp=(tmp*+j)%l;

      char t=s[j]; s[j]=s[tmp]; s[tmp]=t;

    }

      if(dc[]=='A')for(int j=;j<l;j++)add(s[j]-'A');

      else

    {

      int ans=query(l); mask^=ans;

      printf("%d\n",ans);

    }

    }

  return ;

}