题目: https://www.lydsy.com/JudgeOnline/problem.php?id=2555
建立后缀自动机, 就可以直接加入新串了;
出现次数就是 Right 集合的大小, 需要查询 Parent 树上的子树和;
所以可以用 LCT 维护 Parent 树, 因为 Parent 树是有根树所以不需要 makeroot;
代码中的两种 cut 写法都可以, 其实这里的 splay 节点上记的 siz 值不是 splay 子树里的而是原子树 ( Parent 树上) 里的;
注意读入的函数内不改变 mask -_-
splay 用栈时不要改变 x !
代码如下:
- #include
- #include
- #include
- #include
- using namespace std;
- int const xn=1200005,xm=3e6+5;
- int fa[xn],lst=1,cnt=1,l[xn],go[xn][30],siz[xn];
- int pre[xn],c[xn][2],sta[xn],top,lzy[xn],mask;
- char dc[10],s[xm];
- void turn(int x,int w){siz[x]+=w; lzy[x]+=w;}//
- bool isroot(int x){return c[pre[x]][0]!=x&&c[pre[x]][1]!=x;}
- void pushdown(int x)
- {
- if(!lzy[x])return;
- int ls=c[x][0],rs=c[x][1];
- turn(ls,lzy[x]); turn(rs,lzy[x]);
- lzy[x]=0;
- }
- void rotate(int x)
- {
- int y=pre[x],z=pre[y],d=(c[y][1]==x);
- if(!isroot(y))c[z][c[z][1]==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=1]=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][0]==x)^(c[z][0]==y))rotate(x);
- else rotate(y);
- }
- rotate(x);
- }
- }
- void access(int x)
- {
- for(int t=0;x;c[x][1]=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][0],-siz[x]); pre[c[x][0]]=0; c[x][0]=0;//c[x][0]:parent
- }
- void cut(int x)//
- {
- access(x); int y=fa[x]; splay(y);//
- turn(y,-siz[x]); fa[x]=0; c[y][1]=0;
- }
- void add(int w)
- {
- int p=lst,np=++cnt; lst=np; l[np]=l[p]+1; siz[np]=1;
- for(;p&&!go[p][w];p=fa[p])go[p][w]=np;
- if(!p)fa[np]=1,link(np,1);
- else
- {
- int q=go[p][w];
- if(l[q]==l[p]+1)fa[np]=q,link(np,q);
- else
- {
- int nq=++cnt; l[nq]=l[p]+1;
- 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=1;//1
- for(int i=0;i<l;i++)
- {
- if(!go[p][s[i]-'A'])return 0;
- p=go[p][s[i]-'A'];
- }
- access(p); splay(p); return siz[p];//
- }
- int main()
- {
- int Q; scanf("%d",&Q);
- scanf("%s",s+1); int l=strlen(s+1);
- for(int i=1;i<=l;i++)add(s[i]-'A');
- for(int i=1;i<=Q;i++)
- {
- scanf("%s",dc); scanf("%s",s); l=strlen(s);
- int tmp=mask;//!!-_-
- for(int j=0;j<l;j++)
- {
- tmp=(tmp*131+j)%l;
- char t=s[j]; s[j]=s[tmp]; s[tmp]=t;
- }
- if(dc[0]=='A')for(int j=0;j<l;j++)add(s[j]-'A');
- else
- {
- int ans=query(l); mask^=ans;
- printf("%d\n",ans);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2881421.html