题解 P3823【[NOI2017]蚯蚓排队】

· · 题解

相当愚蠢的一道题......

我们发现 k 很小，所以用哈希表在每次合并和分裂的时候维护每个 k 的答案。

然后发现这个队伍是可以直接链表维护的，并且增量只与两端的 k 个有关。于是每次合并把前面队伍的后 k 个和后面队伍的前 k 个拉出来哈希一下合并起来。分裂同理维护。

如果你以为这东西是 O(nk^2+\sum|s|) 过不去的时候，你会看到那个 c\le 1000。于是我们重新分析一下复杂度。如果没有拆开操作的话，那么由于总共只有 O(nk) 段有效子列，所以复杂度是 O(nk)，每次分裂只会增加 O(k^2) 的复杂度和势能，所以总复杂度是 O(nk+ck^2+\sum|s|)，可以接受。

这么水的题是怎么进NOI的

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=3e5+5,K=55,P=1e7+7,P2=998244353;
int n,m,k,l[N],nxt[N],pre[N],bas1[K],hs1[K],hs2[K];char s[P];
int hd[P],Nxt[N*K],Len[N*K],tot,cnt[N*K];ull key[N*K],bas2[K],Hs1[K],Hs2[K];
void add(int L,int h1,ull h2,int v){
    for(int i=hd[h1];i;i=Nxt[i])if(key[i]==h2&&Len[i]==L){cnt[i]+=v;return;}
    Len[++tot]=L,key[tot]=h2,Nxt[tot]=hd[h1],hd[h1]=tot,cnt[tot]=1;
}
int query(int L,int h1,ull h2){
    for(int i=hd[h1];i;i=Nxt[i])if(key[i]==h2&&Len[i]==L)return cnt[i];
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&l[i]),add(1,l[i],l[i],1);
    for(int i=bas1[0]=bas2[0]=1;i<=51;i++)bas1[i]=bas1[i-1]*13%P,bas2[i]=bas2[i-1]*137;
    for(int i=1,op,x,y;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&x,&y);int l1=0,l2=0;
            for(int j=1,t=x;j<=50&&t;l1++,j++,t=pre[t])hs1[j]=(hs1[j-1]+l[t]*bas1[j-1])%P,Hs1[j]=Hs1[j-1]+l[t]*bas2[j-1];
            for(int j=1,t=y;j<=50&&t;l2++,j++,t=nxt[t])hs2[j]=(hs2[j-1]*13+l[t])%P,Hs2[j]=Hs2[j-1]*137+l[t];
            for(int l=2;l<=50&&l<=l1+l2;l++)
                for(int j=1;j<l&&j<=l1;j++)if(l-j<=l2)
                    add(l,(1ll*hs1[j]*bas1[l-j]+hs2[l-j])%P,Hs1[j]*bas2[l-j]+Hs2[l-j],1);
            nxt[x]=y,pre[y]=x;
        }
        else if(op==2){
            scanf("%d",&x);y=nxt[x];int l1=0,l2=0;
            for(int j=1,t=x;j<=50&&t;l1++,j++,t=pre[t])hs1[j]=(hs1[j-1]+l[t]*bas1[j-1])%P,Hs1[j]=Hs1[j-1]+l[t]*bas2[j-1];
            for(int j=1,t=y;j<=50&&t;l2++,j++,t=nxt[t])hs2[j]=(hs2[j-1]*13+l[t])%P,Hs2[j]=Hs2[j-1]*137+l[t];
            for(int l=2;l<=50&&l<=l1+l2;l++)
                for(int j=1;j<l&&j<=l1;j++)if(l-j<=l2)
                    add(l,(1ll*hs1[j]*bas1[l-j]+hs2[l-j])%P,Hs1[j]*bas2[l-j]+Hs2[l-j],-1);
            nxt[x]=0,pre[y]=0;
        }
        else {
            scanf("%s %d",s+1,&k);int ans=1,h1=0,len=strlen(s+1);ull h2=0;
            for(int i=1;i<=k;i++)h1=(h1*13+s[i]-'0')%P,h2=h2*137+s[i]-'0';
            for(int i=k;i<=len;i++){
                ans=1ll*ans*query(k,h1,h2)%P2;
                if(ans==0)break;
                h1=((h1-1ll*(s[i-k+1]-'0')*bas1[k-1]%P+P)*13+(s[i+1]-'0'))%P;
                h2=(h2-(s[i-k+1]-'0')*bas2[k-1])*137+s[i+1]-'0';
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}