题解：P7764 [COCI 2016/2017 #5] Poklon

思路

这题看题面非常莫队（多写一点莫队就知道了），数据也不大，莫队能过，所以写正常莫队就行了。注意奇偶块优化别写错了。还有一点，这题数组中元素小于

10^9

不能直接用数组存每个数的出现次数，要离散化，如果不会可以看我的代码，但是 map 常数有点大，如果数据大建议换一种方式离散化。其他细节可以看代码。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct A{
	int l,r,k,id;
}q[500005];
bool cmp(A x,A y){//奇偶块优化 
	if(x.k!=y.k) return x.l<y.l;
	if(x.k%2==1) return x.r<y.r;
	return x.r>y.r;
}
int n,Q,a[500005],b[500005],l=1,r,cnt,ans[500005],v[500005],kuai,ll,rr;
map<int,int> mp;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>Q;
	kuai=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	for(int i=1;i<=Q;i++){
		cin>>q[i].l>>q[i].r;
		q[i].k=(q[i].l-1)/kuai+1;//记哪一个块，用来奇偶块优化 
		q[i].id=i;//优化后问题顺序会变，所以要记提问的原位置 
	}
	sort(q+1,q+1+Q,cmp);//奇偶排序 
	sort(b+1,b+1+n);//排序离散化 
	for(int i=1,j=1;i<=n;i++){
		if(b[i]!=b[i-1]){
			mp[b[i]]=j;//记录离散化结果 
			j++;
		}
	}
	for(int i=1;i<=n;i++) a[i]=mp[a[i]];//该原数组为离散化后的 
	for(int i=1;i<=Q;i++){
		ll=q[i].l,rr=q[i].r;
		while(r<rr){//顺序很重要，可以记一下 
			r++;
			if(v[a[r]]==2) cnt--;
			v[a[r]]++;
			if(v[a[r]]==2) cnt++;
		}
		while(l>ll){
			l--;
			if(v[a[l]]==2) cnt--;
			v[a[l]]++;
			if(v[a[l]]==2) cnt++;
		}
		while(l<ll){
			if(v[a[l]]==2) cnt--;
			v[a[l]]--;
			if(v[a[l]]==2) cnt++;
			l++;
		}
		while(r>rr){
			if(v[a[r]]==2) cnt--;
			v[a[r]]--;
			if(v[a[r]]==2) cnt++;
			r--;
		}
		ans[q[i].id]=cnt;//注意记在原位置上而不是现在的位置i (我因为这个考试挂了 
	}
	for(int i=1;i<=Q;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

题解：P7764 [COCI 2016/2017 #5] Poklon

文章操作

思路

代码

相关推荐

评论

题解：P7764 [COCI 2016/2017 #5] Poklon