记录编号	600102	评测结果	EWWWWWWWWE
题目名称	[SDOI 2009] HH的项链	最终得分	0
用户昵称	会挽弯弓满月	是否通过	未通过
代码语言	C++	运行时间	3.285 s
提交时间	2025-04-15 21:13:02	内存使用	5.33 MiB

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=5e4+10,M=2e5+10;
ll n,q;
ll a[N],id[N];
struct node{
	ll l,r,id;
}e[N];
bool cmp(node a1,node a2) {
	if(id[a1.l]!=id[a2.l]) return id[a1.l]<id[a2.l];
	if(id[a1.l]&1) return a1.r<a2.r;
	return a1.r>a2.r;
}
int tot[M];
ll now;
void add(int x){
	if(tot[a[x]]==0) now++;
	tot[a[x]]++;
}
void del(int x){
	tot[a[x]]--;
	if(tot[a[x]]==0) now--;
}
ll len,cnt;
ll ans[N];
int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	scanf("%lld",&n);
	len=sqrt(n);
	cnt=n/len;
	if(n%len) cnt++;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		id[i]=(i-1)/len+1;
	}
	scanf("%lld",&q);
	for(int i=1;i<=q;i++){
		scanf("%lld%lld",&e[i].l,&e[i].r);
		e[i].id=i;
	}
	sort(e+1,e+q+1,cmp);
	ll l=1,r=0;
	for(int i=1;i<=q;i++){
		while(l<e[i].l) del(l++);
		while(l>e[i].l) add(--l);
		while(r<e[i].r) add(++r);
		while(r>e[i].r) del(r--);
		ans[e[i].id]=now;
	}
	for(int i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}