题解

思路概述

• 排列 p 规定了模式序列的相对大小关系。先读取 h 时，把每个数替换成它在当前窗口中的“秩”。若窗口内 n 个数与 a 的相对次序一致，则子串匹配成功。
• 具体做法：先为模式 a 构造 Fenwick 树（BIT）求排名 f[i]：f[i] 表示 a_i 在前缀里有多少元素比它小（即离散化后的 rank）。
• 然后对文本 b，使用同样的 BIT 滑动窗口：每加入一个元素，就比较当前 rank 与模式 f，若 query(b[i]) == f[j+1] 则继续，否则回退到 KMP 的失配指针（border 数组）。border 通过同样的 rank 序列构建。
• 当匹配长度达到 n 时，就找到一个合法区间，其起始位置就是 i-n+1。

复杂度

• Fenwick 树维护 O(log n)，KMP 核心循环遍历 m 次，每次仅做若干 log n 查询，整体复杂度 O((n+m) log n)。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define sec second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define pb push_back
const int inf=0x3f3f3f3f;
const int mod=998244353;
int n,m,k,tmp[1000010],a[1000010],b[1000010],f[1000010],g[1000010];
int border[1000010];
int c[1000010];
vector<int>ans;
void init(){memset(c,0,sizeof(c));}
int lowbit(int x){return x&(-x);}
void update(int x,int v){while(x<=m)c[x]+=v,x+=lowbit(x);}
int query(int x){int ans=0;while(x)ans+=c[x],x^=lowbit(x);return ans;}
void kmp()
{
	init();
	border[1]=0;
	for(int i=2,j=0;i<=n;i++)
	{
//		cout<<"      "<<i<<" "<<j<<" "<<a[i]<<" "<<query(a[i])<<endl; 
		while(j&&query(a[i])!=f[j+1])
		{
			for(int k=i-border[j]-1;k>=i-j;k--)update(a[k],-1);
			j=border[j];
		}
//		cout<<"      "<<i<<" "<<j<<endl; 
		if(query(a[i])==f[j+1])
		{
			j++;
			update(a[i],1);
		}
		border[i]=j;
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){int x;cin>>x;a[x]=i;}
	for(int i=1;i<=m;i++)cin>>b[i],tmp[i]=b[i];
	sort(tmp+1,tmp+m+1);
	k=unique(tmp+1,tmp+m+1)-tmp-1;
	for(int i=1;i<=m;i++)b[i]=lower_bound(tmp+1,tmp+k+1,b[i])-tmp;
	
	for(int i=1;i<=n;i++)
	{
		f[i]=query(a[i]-1);
		update(a[i],1);
//		cout<<"   "<<i<<" "<<f[i]<<endl;
	}
	f[n+1]=n+1; 
	
	kmp();
//	for(int i=1;i<=n;i++)cout<<"border["<<i<<"]="<<border[i]<<endl;
	
	init();
	for(int i=1,j=0;i<=m;i++)
	{
//		cout<<"   "<<b[i]<<" "<<query(b[i])<<" "<<query(m)<<endl;
		while(j&&query(b[i])!=f[j+1])
		{
			for(int k=i-border[j]-1;k>=i-j;k--)update(b[k],-1);
			j=border[j];
		}
		if(query(b[i])==f[j+1])
		{
			j++;
			update(b[i],1);
		}
//		cout<<"match:"<<i<<" "<<j<<endl;
		if(j==n)
		{
			ans.pb(i-n+1);
//			for(int k=i-border[j]-1;k>=i-j;k--)update(b[k],-1);
//			j=border[j];
		}
	}
	
	cout<<ans.size()<<endl;
	for(auto x:ans)cout<<x<<" ";
	cout<<endl;
	return 0;
}