记录编号	600076	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	dream	是否通过	通过
代码语言	C++	运行时间	3.635 s
提交时间	2025-04-15 20:01:43	内存使用	8.76 MiB

#include<bits/stdc++.h>
using namespace std;
const int V=1000005,N=V,M=V;
struct node{
	int x,y,id;
	bool operator < (const node &t) const{
		if(x==t.x) return y<t.y;
		return x<t.x;
	}
}q[M];
int n,m;
int b[V];
int a[N];
int ans[M];
int nx=0,ny=0,an=0;
void mbr(int x,int y){
	for(int i=nx;i<=x-1;i++){
		if(b[a[i]]==1) an--;
		b[a[i]]--;
//		cout<<"a"<<an;
	}
	for(int i=ny+1;i<=y;i++){
		if(!b[a[i]]) an++;
		b[a[i]]++;
//		cout<<"b"<<i<<" "<<an;
	}
	nx=x,ny=y;
//	cout<<nx<<" "<<ny<<"\n";
}
void mbl(int x,int y){
	for(int i=nx;i<=x-1;i++){
		if(b[a[i]]==1) an--;
		b[a[i]]--;
	}
	for(int i=ny;i>=y+1;i--){
		if(b[a[i]]==1) an--;
		b[a[i]]--;
	}
	nx=x,ny=y;	
}
void md(){
	for(int i=1;i<=m;i++){
		node t=q[i];
		if(t.y>=ny)
			mbr(t.x,t.y);
		else mbl(t.x,t.y);
		ans[t.id]=an;
//		cout<<nx<<" "<<ny<<"\n";
	}
}
inline void read(int &x){
	int sum=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	x=sum;
}
inline void write(int x){
	if(x/10) write(x/10);
	putchar(x%10+'0');
}
int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	read(m);
	for(int i=1;i<=m;i++){
		int x,y;
		read(x),read(y);
		q[i]={x,y,i};
	}
	sort(q+1,q+m+1);
	md();
	for(int i=1;i<=m;i++){
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}