BZOJ 2555: SubString(后缀自动机+lct)-程序员宅基地

传送门

解题思路

　　第二个操作其实就是把\(T\)在\(S\)上跑一遍匹配然后输出最后那个匹配点\(right\)集合的大小。现在考虑如何动态维护，发现\(right\)集合的转移为\(siz_{fa_i}=\sum siz_i\)，那么假如一个字符其实就是给\(parent\)树上这个点的每个祖先\(+1\)，这样就可以\(lct\)维护。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
 
using namespace std;
const int N=600005<<1;
 
int Q,lstans,stk[N],top;
char s[N];
 
struct LCT{
    int fa[N],ch[N][2],siz[N],tag[N];
    bool judge(int x){
        return (x==ch[fa[x]][1]);
    }
    bool isroot(int x){
        return (x!=ch[fa[x]][0] && x!=ch[fa[x]][1]);
    }
    void add(int x,int y){
        if(x) siz[x]+=y,tag[x]+=y;
    }
    void pushdown(int x){
        if(tag[x]){
            add(ch[x][0],tag[x]); add(ch[x][1],tag[x]);
            tag[x]=0;
        }
    }
    void pd(int x) {
        while(!isroot(x)) stk[++top]=x,x=fa[x];
        stk[++top]=x;
        while(top) pushdown(stk[top--]);
    }
    void rotate(int x){
        int y=fa[x],z=fa[y]; bool chk=judge(x);
        if(!isroot(y)) ch[z][judge(y)]=x;
        ch[y][chk]=ch[x][chk^1]; fa[ch[x][chk^1]]=y;
        ch[x][chk^1]=y; fa[y]=x; fa[x]=z;
    }
    void splay(int x){
        pd(x);
        for(;!isroot(x);rotate(x))
            if(!isroot(fa[x])) rotate(judge(fa[x])==judge(x)?fa[x]:x);
    }
    void access(int x){
        for(int y;x;y=x,x=fa[x])
            splay(x),ch[x][1]=y;
    }
    void link(int x,int y){
        fa[x]=y; access(y); splay(y); add(y,siz[x]);
    }
    void cut(int x){
        access(x); splay(x); add(ch[x][0],-siz[x]);
        ch[x][0]=fa[ch[x][0]]=0;
    }
}lct;
 
struct SAM{
    int ch[N][28],fa[N],l[N],lst,cnt;
    void Insert(int c){
        int p=lst,np=++cnt; l[np]=l[p]+1; lst=np; lct.siz[np]=1;
        for(;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
        if(!p) fa[np]=1,lct.link(np,1);
        else {
            int q=ch[p][c];
            if(l[p]+1==l[q]) fa[np]=q,lct.link(np,q);
            else {
                int nq=++cnt; l[nq]=l[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[nq]));
                fa[nq]=fa[q]; lct.link(nq,fa[q]); lct.cut(q);
                fa[q]=fa[np]=nq; lct.link(np,nq); lct.link(q,nq);
                for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
    }
    int query(){
        int len=strlen(s),now=1;
        for(int i=0;i<len;i++){
            if(ch[now][s[i]-'A']) now=ch[now][s[i]-'A'];
            else return 0;
        }
        lct.splay(now); return lct.siz[now];    
    }
}sam;
 
void work(){
    int len=strlen(s),tmp=lstans;
    for(int i=0;i<len;i++) {
        tmp=(tmp*131+i)%len;
        swap(s[i],s[tmp]);
    }
}
 
inline void init(){
    int len; sam.cnt=sam.lst=1;
    scanf("%d%s",&Q,s); len=strlen(s);
    for(int i=0;i<len;i++) sam.Insert(s[i]-'A');
}
 
void solve(){
    char t[10]; int len,tmp;
    scanf("%s%s",t+1,s); work(); len=strlen(s);
    if(t[1]=='Q') tmp=sam.query(),printf("%d\n",tmp),lstans^=tmp;
    else for(int i=0;i<len;i++) sam.Insert(s[i]-'A');
}
 
int main(){
    init(); 
    while(Q--) solve();
    return 0;
}