自动搬运

查看原文

来自洛谷，原作者为

	FunnyCreatress AFOed.

搬运于2025-08-24 21:53:07，当前版本为作者最后更新于2021-03-27 23:14:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

我们发现 $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;
}