测评记录

#include<cstdio> 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=1e6+5;
int n,m,len;
int w[N],ans[N];
struct Query{
	int id,l,r;
}q[N];
int cnt[N];

int get(int x) {
	return x/len;
} 

bool cmp(const Query& a,const Query& b) {
	int i=get(a.l),j=get(b.l);
	if(i!=j) return i<j;
	if(i%2) return a.r<b.r;
	return a.r>b.r;
}

void add(int x,int &res) {
	if(!cnt[x]) res++;
	cnt[x]++;	
}

void del(int x,int &res) {
	cnt[x]--;
	if(!cnt[x]) res--; 
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	scanf("%d",&m);
	len=sqrt(n);
	
	for(int i=0;i<m;i++) {
		int l,r;
		scanf("%d%d",&l,&r);
		q[i]={i,l,r};
	}
	
	sort(q,q+m,cmp);
	
	for(int k=0,i=0,j=1,res=0;k<m;k++) {
		int id=q[k].id,l=q[k].l,r=q[k].r;
		while(i<r) add(w[++i],res);
		while(i>r) del(w[i--],res);
		while(j<l) del(w[j++],res);
		while(j>l) add(w[--j],res);
		ans[id]=res;
	}
	
	for(int i=0;i<m;i++) printf("%d\n",ans[i]);
	
	return 0;
}