并不对劲的复健训练-p5212 SubString

淡淡的烟草味﹌ 2023-08-17 16:46 15阅读 0赞

##### 题目大意 #####

有一个串\\(s\\)，一开始只知道它的一个前缀。有\\(q\\)（\\(q\\leq 10^4\\)）个操作，操作有两种：1.给一个字符串，表示\\(s\\)（\\(s\\)总长\\(\\leq 6\\times 10^5\\)）当前未知部分的前缀；2.给一个字符串，问\\(s\\)的已知部分中有几个子串和该串相同，询问串总长\\(\\leq 3\\times 10^6\\)。强制在线。

##### 题解 #####

后缀自动机一边extend一边用LCT维护right集合大小。

##### 代码 #####

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];~k;k=nxt[k])
    #define LL long long
    #define maxn 600007
    #define maxm 1200007
    #define maxk 3000007
    #define ls son[u][0]
    #define rs son[u][1]
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    namespace LCT
    {
        int son[maxm][2],fa[maxm],mk[maxm],num[maxm],stk[maxm],tp;
        void mark(int u,int k){if(u)mk[u]+=k,num[u]+=k;}
        void pd(int u){if(u&&mk[u])mark(ls,mk[u]),mark(rs,mk[u]),mk[u]=0;}
        int nort(int u){return son[fa[u]][0]==u||son[fa[u]][1]==u;}
        int getso(int u){return son[fa[u]][0]!=u;}
        void rot(int u)
        {
            int fu=fa[u],ffu=fa[fu],l=getso(u),fl=getso(fu),r=l^1,rson=son[u][r];
            son[u][r]=fu,son[fu][l]=rson;if(nort(fu))son[ffu][fl]=u;if(rson)fa[rson]=fu;fa[u]=ffu,fa[fu]=u;
        }
        void splay(int u)
        {
            int v=u;stk[tp=1]=v;while(nort(v))stk[++tp]=v=fa[v];
            while(tp)pd(stk[tp--]);
            while(nort(u)){int fu=fa[u];if(nort(fu))rot(getso(u)^getso(fu)?u:fu);rot(u);}   
        }
        void acs(int u){for(int v=0;u;v=u,u=fa[u])splay(u),rs=v;}
        void cut(int u){acs(u),splay(u),fa[ls]=0,ls=0;}//fth[u]=v
        void link(int u,int v){fa[u]=v;}
        void opt(int u,int k){acs(u),splay(u),mark(u,k);}
        void add(int u,int v){num[u]=num[v];}
        int ask(int u){splay(u);return num[u];}
    }
    int mask,n,len,ch[maxm][26],dis[maxm],r[maxm],fa[maxm],lst,cntnd,rt,ans;
    char s[maxk],t[6];
    int gx(char c){return c-'A';}
    void ext(char c)
    {
        int p=lst,np=++cntnd,v=gx(c);dis[np]=dis[p]+1,lst=np;
        for(;p&&!ch[p][v];p=fa[p])ch[p][v]=np;
        if(!p)fa[np]=rt,LCT::link(np,rt);
        else
        {
            int q=ch[p][v];
            if(dis[q]==dis[p]+1)fa[np]=q,LCT::link(np,q);
            else
            {
                int nq=++cntnd;dis[nq]=dis[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                LCT::cut(q),LCT::add(nq,q),LCT::link(nq,fa[q]),LCT::link(q,nq),LCT::link(np,nq);
                fa[nq]=fa[q],fa[np]=fa[q]=nq;
                for(;p&&ch[p][v]==q;p=fa[p])ch[p][v]=nq;
            }
        }
        LCT::opt(np,1);
    }
    int main()
    {
        rt=lst=++cntnd;
        scanf("%d%s",&n,s);len=strlen(s);
        rep(i,0,len-1)ext(s[i]);
        while(n--)
        {
            scanf("%s%s",t,s),len=strlen(s);int msk=mask;
            rep(i,0,len-1)
            {
                msk=(msk*131+i)%len;
                swap(s[i],s[msk]);
            }
            if(t[0]=='Q')
            {
                int now=rt;
                rep(i,0,len-1)
                {
                    int v=gx(s[i]);
                    now=ch[now][v];
                    if(!now)break;
                }
                if(!now)ans=0;
                else {ans=LCT::ask(now);}
                write(ans);
                mask^=ans;
            }
            else{rep(i,0,len-1)ext(s[i]);}
        }
        return 0;
    }

##### 一些感想 #####

既弱智又星际怎么办，在线等，挺急的！

转载于:https://www.cnblogs.com/xzyf/p/11582758.html