考虑设计一个哈希函数 \(hash(x) = f(x) \times base^x\)。
其中 \(f(x)\) 表示 \(\sum_{j=1}^{i-1} [j <i]\)。
然后类似于滑动窗口计算区间哈希值，加入一个数就计算贡献，减去一个数就计算这个数产生了贡献，两个东西都可以树状数组维护，那么愉快做完了。
#include<bits/stdc++.h>
#define int unsigned long long
#define lowbit(x)(x&(-x))
using namespace std;
//f(x) 表示 x 前面小于 x 的数的数量
//hash(x) = 1331^(x)*f(x)
const int maxn = 1e6+114;
const int base = 1145141;
int tr[maxn][2],_pow[maxn];
void add(int x,int v,int type){
while(x<maxn){
tr[x][type]+=v;
x+=lowbit(x);
}
}
int pre(int x,int type){
int res=0;
while(x>0){
res+=tr[x][type];
x-=lowbit(x);
}
return res;
}
int a[maxn],b[maxn],n,m,s,val1,ans;
queue<int> q;
signed main(){
_pow[0]=1;
for(int i=1;i<maxn;i++) _pow[i]=_pow[i-1]*base;
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]++;
}
for(int i=1;i<=m;i++){
cin>>b[i];
b[i]++;
val1+=_pow[i]*pre(b[i]-1,0);
add(b[i],1,0);
}
for(int i=0;i<maxn;i++) tr[i][0]=tr[i][1]=0;
int val2=0,sum=0;
for(int i=1;i<=n;i++){
val2+=_pow[i]*pre(a[i]-1,0);
add(a[i],1,0);
add(a[i],_pow[i],1);
sum+=_pow[i];
if(i>m){
val2-=(sum-pre(a[i-m],1));
add(a[i-m],-1,0);
add(a[i-m],-_pow[i-m],1);
sum-=_pow[i-m];
}
if(i>=m){
if(val2==val1*_pow[i-m]){
q.push(i-m+1);
}
}
}
cout<<q.size()<<'\n';
while(q.size()>0){
cout<<q.front()<<'\n';
q.pop();
}
return 0;
}
/*
9 6 10
5 6 2 10 10 7 3 2 9
1 4 4 3 2 1
*/
感觉最多评绿吧，再高就恶评了（逃。