专栏文章

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

bbravo11111111
P7764题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minv74lz
此快照首次捕获于
2025/12/02 08:53
3 个月前
此快照最后确认于
2025/12/02 08:53
3 个月前
查看原文

解题思路:

这道题我们可以考虑用莫队做，首先先对数列进行离散化，因为这题 aiai 的大小是 10910^9 显然桶存不下。然后在莫队过程中，当加入一个数时，如果这个数出现了两次，将答案加一，如果出现三次，就将答案减一。减去一个数时如果这个数的个数被减到到两次，将答案加一，如果这个数被减到只剩一次，则将答案减一。然后我们就可以愉快的水一道蓝了。

AC代码：

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int l,r,id;
} qu[500001];
int n,q,pos[500001],len,a[500001],vis[500001],b[500001],sum,ans[500001];
bool cmp(node s1,node s2) {
	if(pos[s1.l]!=pos[s2.l])return s1.l<s2.l;
	if(pos[s1.l]%2==1)return s1.r<s2.r;
	return s1.r>s2.r;
}
void add(int p) {
	vis[a[p]]++;
	if(vis[a[p]]==2)sum++;
	if(vis[a[p]]==3)sum--;
	return ;
}
void del(int p) {
	vis[a[p]]--;
	if(vis[a[p]]==2)sum++;
	if(vis[a[p]]==1)sum--;
	return ;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	len=sqrt(n);
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		pos[i]=(i-1)/len+1;
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int t=unique(b+1,b+n+1)-b-1;
	for(int i=1; i<=n; i++)a[i]=lower_bound(b+1,b+t+1,a[i])-b;
	for(int i=1; i<=q; i++) {
		int x,y;
		cin>>x>>y;
		qu[i].l=x;
		qu[i].r=y;
		qu[i].id=i;
	}
	sort(qu+1,qu+q+1,cmp);
	int L=1,R=0;
	for(int i=1; i<=q; i++) {
		while(L>qu[i].l)add(--L);
		while(R<qu[i].r)add(++R);
		while(L<qu[i].l)del(L++);
		while(R>qu[i].r)del(R--);
		ans[qu[i].id]=sum;
	}
	for(int i=1; i<=q; i++)cout<<ans[i]<<"\n";
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...