#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 200005;
const int p = 1e7+7;
const int MOD = 998244353;
#define ull unsigned long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,tot,f[p+5],a[M],h1[M],H1[M],b1[M],pre[M],nxt[M];
ull h2[M],H2[M],b2[M];char s[p];
struct edge{ull h2;int c,L,next;}e[M*55];
void add(int L,int h1,ull h2,int c)
{
	//printf(">> %d %d %u %d\n",L,h1,h2,c);
	for(int i=f[h1];i;i=e[i].next) if(e[i].h2==h2)
		{e[i].c+=c;return ;}
	e[++tot]=edge{h2,c,L,f[h1]},f[h1]=tot;
}
int ask(int L,int h1,ull h2)
{
	for(int i=f[h1];i;i=e[i].next)
		if(e[i].L==L && e[i].h2==h2) return e[i].c;
	return 0;
}
void work()
{
	int op=read();
	if(op==1 || op==2)
	{
		int x=read(),y=0,A=0,B=0,f=(op==1)?1:-1;
		y=(op==1)?read():nxt[x];
		for(int i=1,t=x;i<=50 && t;i++,t=pre[t],A++)
			h1[i]=(h1[i-1]+a[t]*b1[i-1])%p,h2[i]=h2[i-1]+a[t]*b2[i-1];
		for(int i=1,t=y;i<=50 && t;i++,t=nxt[t],B++)
			H1[i]=(H1[i-1]*13+a[t])%p,H2[i]=H2[i-1]*371+a[t];
		for(int l=2;l<=50 && l<=A+B;l++)
			for(int i=1;i<l && i<=A;i++) if(l-i<=B)
				add(l,(1ll*h1[i]*b1[l-i]+H1[l-i])%p
					,h2[i]*b2[l-i]+H2[l-i],f);
		if(op==1) nxt[x]=y,pre[y]=x;
		else nxt[x]=pre[y]=0;
		return ;
	} 
	scanf("%s",s+1);
	int l=strlen(s+1),k=read(),h1=0,ans=1;ull h2=0;
	for(int i=1;i<=l;i++) s[i]-='0';
	for(int i=1;i<=k;i++) h1=(h1*13+s[i])%p,h2=h2*371+s[i];
	for(int i=k;i<=l;i++)
	{
		ans=1ll*ans*ask(k,h1,h2)%MOD;
		if(ans==0) break;
		h1=(h1-1ll*s[i-k+1]*b1[k-1]%p)*13+s[i+1];
		h1=(h1%p+p)%p;
		h2=(h2-s[i-k+1]*b2[k-1])*371+s[i+1];
	}
	printf("%d\n",ans);
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),add(1,a[i],a[i],1);
	for(int i=b1[0]=b2[0]=1;i<=50;i++)
		b1[i]=b1[i-1]*13%p,b2[i]=b2[i-1]*371;
	while(m--) work();
}

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

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