区间数颜色。
直接莫队就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10000005,M=10000005;
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-'){f=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int a[N],pos[N],n,m,ANS[N],ans=0,cnt[N],num[N],A[N];
struct node{
int l,r,id;
}q[N];
inline bool cmp(node a,node b) {
return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
}
void update(int id,int f){
int x=a[id];
if(f==1){
cnt[x]++;
if(cnt[x]==1) ans++;
}
else{
cnt[x]--;
if(cnt[x]==0) ans--;
}
return ;
}
int main(){
n=read();
int op=sqrt(n);
for(int i=1;i<=n;i++){
A[i]=read();
a[i]=A[i];
pos[i]=i/op;
}
m=read();
sort(A+1,A+n+1);
int nn=unique(A+1,A+n+1)-A-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(A+1,A+nn+1,a[i])-A;
for(int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read(),q[i].id=i;
}
sort(q+1,q+m+1,cmp);
for(int i=1,l=1,r=0;i<=m;i++){
int ql=q[i].l,qr=q[i].r;
while(l<ql) ans-=!--cnt[a[l++]];
while(l>ql) ans+=!cnt[a[--l]]++;
while(r<qr) ans+=!cnt[a[++r]]++;
while(r>qr) ans-=!--cnt[a[r--]];
ANS[q[i].id]=ans;
}
for(int i=1;i<=m;i++){
printf("%d
",ANS[i]);
}
return 0;
}