写一篇题解纪念我死去的 $E$ 题。

场上 $20min$ 就会了，结果挂分挂得很惨，数组开小了导致的，开大以后就过了，，，，

我们注意到我们需要的是相对大小，然后这个东西显然就不能直接哈希了，不过我们可以哈希点别的。

我们先把 $t$ 离散化掉，然后把它的哈希干出来，然后我们要快速维护一个固定长度的滑动窗口，这个窗口里存放了某一个区间里的哈希。

我们可以考虑对于一个数列，它的哈希可以写成

$\sum rk_i*p^i$

这样写的好处就是对于每一个位置 $p^i$ 是静态的，我们不需要处理一些奇奇怪怪的情况。

具体的写法我会在代码里展示

#include<bits/stdc++.h>
#define base 13331
#define int long long
using namespace std;
int p[1000005];
int s[1000005],t[1000005],num[1000005];
int C[10005];int n,m,l;
int c[10005];
inline int lowbit(int x){return x&-x;}
inline void add(int x,long long K,bool tmp){
	for(int i=x; i<=l; i+=lowbit(i)){
		if(tmp)C[i]+=K,c[i]++;
		else C[i]-=K,c[i]--;
	}
}
inline long long ask(int x){
	long long S=0;
	for(int i=x; i; i-=lowbit(i))S+=C[i];
	return S;
}inline int akk(int x){
	int s=0;
	for(int i=x; i; i-=lowbit(i))s+=c[i];
	return s;
}bool vis[1000005];
signed main(){
	scanf("%lld%lld%lld",&n,&m,&l);
	p[0]=1;for(int i=1;i <=n; i++)p[i]=p[i-1]*1ll*base;
	for(int i=1; i<=n; i++)scanf("%lld",&s[i]);
	for(int i=1; i<=m; i++)scanf("%lld",&t[i]),num[++num[0]]=t[i];
	sort(num+1,num+1+num[0]);
	int hshh=0;//这是 T 的哈希 
	for(int i=1; i<=m; i++)t[i]=lower_bound(num+1,num+1+num[0],t[i])-num,hshh=hshh+t[i]*1ll*p[i];
	int hssh=0;//这是目前的滑动窗口里的哈希 
	for(int i=1; i<=m; i++)hssh+=(akk(s[i]-1)+1)*1ll*p[i],add(s[i],p[i],1),hssh+=(ask(l)-ask(s[i]));//,cout<<akk(s[i]-1)+1<<endl;
	
	int cnt=0;
	for(int i=1; i+m-1<=n; i++){
		vis[i]=(hssh==hshh);//判断是否合法 
		cnt+=vis[i];
		hshh=hshh*1ll*base;//对于 T 的哈希向后移动一位 
		hssh-=(akk(s[i]-1)+1)*1ll*p[i];//去掉第i个位置的贡献 
		hssh-=(ask(l)-ask(s[i]));//因为可能有比 S_i 大的数，所以我们要把它们的名次贡献去掉 
		add(s[i],p[i],0);
		if(i+m<=n){
			
			//以下是加贡献的部分，和上面基本一致 
			hssh+=(akk(s[i+m]-1)+1)*1ll*p[i+m];
			add(s[i+m],p[i+m],1);
			hssh+=(ask(l)-ask(s[i+m]));
		}
	}printf("%d\n",cnt);
	for(int i=1; i<=n; i++){
		if(vis[i])printf("%d\n",i);
	}
	return 0;
}/*
10 8 10000
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8

10 4 10000
1 2 1 3 1 4 1 5 1 6
1 2 1 2
*/