BZOJ 1461 题解

考虑设计一个哈希函数 \(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
*/

感觉最多评绿吧，再高就恶评了（逃。