期望得分36

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,t,l,r,a[N],ans[N];
map<int,int> M;
struct hhh
{
	int l,r,id;
}v[N];
inline bool cmp(hhh x,hhh y)
{
	if(x.l/t!=y.l/t) return x.l/t<y.l/t;
	if((x.l/t)&1) return x.r<y.r;//奇偶数优化,使相邻区间的数尽量靠近分界线,卡常用 
	else return x.r>y.r;
}
bool cmp1(hhh x,hhh y)
{
	return x.id<y.id;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n; t=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	cin>>m;
	for(int i=1;i<=m;i++) scanf("%d%d",&v[i].l,&v[i].r),v[i].id=i;
	sort(v+1,v+m+1,cmp);
	l=1; r=0;
	for(int i=1;i<=m;i++)
	{
		if(r<v[i].r)
		{
			for(int j=r+1;j<=v[i].r;j++)
			{
				if(!M[a[j]]) M[a[j]]=1;
				else M[a[j]]++;
			}
		}
		else
		{
			for(int j=r;j>v[i].r;j--)
			{
				M[a[j]]--;
				if(!M[a[j]]) M.erase(a[j]);
			}
		}
		if(l<v[i].l)
		{
			for(int j=l;j<v[i].l;j++)
			{
				M[a[j]]--;
				if(!M[a[j]]) M.erase(a[j]);			
			}			
		}
		else
		{
			for(int j=l-1;j>=v[i].l;j--)
			{
				if(!M[a[j]]) M[a[j]]=1;
				else M[a[j]]++;
			}
		}
		l=v[i].l; r=v[i].r;
		ans[v[i].id]=M.size();
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}