自动搬运

查看原文

来自洛谷，原作者为

	konjakujelly AFOer

搬运于2025-08-24 22:17:13，当前版本为作者最后更新于2022-03-24 19:48:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

第一眼看到题目，觉得是 kmp+平衡树，仔细一做，结果写出了 kmp+线段树（前置知识）

解法

读题我们知道，这是一道 kmp，比较是用的每个数的大小关系

上来我直接算出每个数加入时的排名，用这个跑了一遍 kmp（WA 声一片~）

仔细读题，发现 $S$ 只有25，所以就有很多重复的号码，出现正确性问题

那么，我们可以多记录一个值，与自己相同的数有多少个，与排名一起判断，就能保证正确性

我们可以用线段树维护这个 kmp，一个数只会进出线段树各一次，所以时间复杂度为 $\Theta(\log{n}+\log{k})$ ，完美通过， $73ms$ ，最优解第四

CODE

代码如下

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5+10;
int n,k,s,cnt,hed,res;
int nex[MAX],rnk[MAX],sum[MAX],a[MAX],b[MAX],ans[MAX];
int ls[110];
inline int read() {
	int x = 0;
	char ch = getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
//线段树
void build(int l,int r,int lr){
	ls[lr]=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(l,mid,lr<<1),build(mid+1,r,lr<<1|1);
}
void add(int l,int r,int x,int v,int lr){
	ls[lr]+=v;
	if(l==r) return;
	int mid = (l+r)>>1;
	if(x<=mid) add(l,mid,x,v,lr<<1);
	else add(mid+1,r,x,v,lr<<1|1);
}
int query(int l,int r,int L,int R,int lr){
	if(R<L) return 0;
	if(l>=L and r<=R) return ls[lr];
	int mid=(l+r)>>1,res=0;
	if(mid>=L) res=query(l,mid,L,R,lr<<1);
	if(mid<R) res+=query(mid+1,r,L,R,lr<<1|1);
	return res;	
}
//处理 next 数组，初始化
void init(){
	for(int i = 1;i<=k;++i) add(1,s,b[i],1,1),rnk[i]=query(1,s,1,b[i]-1,1),sum[i]=query(1,s,b[i],b[i],1);
	build(1,s,1);
	int p=0;
	for(int i = 2;i<=k;++i){
		add(1,s,b[i],1,1);
		int l=query(1,s,1,b[i]-1,1),r=query(1,s,b[i],b[i],1);
		while(p and (l!=rnk[p+1] or r!=sum[p+1])){
			for(int j = i-p;j<i-nex[p];j++) {
				add(1,s,b[j],-1,1);
				if(b[j]==b[i]) --r;
				if(b[j]<b[i]) --l;
			}
			p=nex[p];
		}
		if(l==rnk[p+1] and r==sum[p+1]) p++;
		nex[i] = p;
	}
	build(1,s,1);
}
signed main() {
// 	freopen(".in","r",stdin);
// 	freopen(".out","w",stdout);
	n = read(),k = read(),s = read();
	for(int i = 1;i<=n;++i) a[i]=read();
	for(int i = 1;i<=k;++i) b[i]=read();
	init();
	int p = 0;
	for(int i = 1;i<=n;++i){
		add(1,s,a[i],1,1);
		int l=query(1,s,1,a[i]-1,1),r=query(1,s,a[i],a[i],1);//提前记录，以免时间爆炸
		while(p and (l!=rnk[p+1] or r!=sum[p+1])) {
			for(int j = i-p;j<i-nex[p];++j) {
				add(1,s,a[j],-1,1);
				if(a[j]==a[i]) r--;//更新当前的排名与相同字符数
				if(a[j]<a[i]) l--;
			}
			p=nex[p];
		}
		if(l==rnk[p+1] and r==sum[p+1])++p;
		if(p==k) ans[++res]=i-k+1;
	}
	printf("%d\n",res);
	for(int i = 1;i<=res;++i) printf("%d\n",ans[i]);
	return 0;
}