这题在线做很麻烦，所以我们选择离线。
首先预处理出数组next[i]表示i这个位置的颜色下一次出现的位置。
然后对与每种颜色第一次出现的位置x,将a[x]++。
将每个询问按左端点排序，再从左往右扫，将next[i]++，如果是询问就先返回sum[r]-sum[l-1](sum是a的前缀和)。其中前缀和可以用树状数组维护。
因为做一个询问之前l到r的所有颜色都加且仅加了1，所以答案就是sum[r]-sum[l-1]。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline char nc(){
static char buf[],*p1=buf,*p2=buf;
if(p1==p2){
p2=(p1=buf)+fread(buf,,,stdin);
if(p1==p2)return EOF;
}
return *p1++;
}
inline void read(int& x){
char c=nc(),b=;
for(;!(c>=''&&c<='');c=nc())if(c=='-')b=-;
for(;c>=''&&c<='';x=x*+c-,c=nc());x*=b;
}
struct ask{
int s,e,f;
}b[];
inline bool cmp(ask x,ask y){
return x.s<y.s;
}
int ans[],i,j,k=,n,a[],last[],m,c[],x,y,next[];
inline int lowbit(int x){
return x&(-x);
}
inline void update(int x){
for(int i=x;i<=n;i+=lowbit(i))c[i]++;
}
inline int query(int x){
int ans=;
for(int i=x;i>;i-=lowbit(i))ans+=c[i];
return ans;
}
int main()
{
read(n);
for(i=;i<=n;i++)read(a[i]);
read(m);
for(i=;i<=m;i++)read(b[i].s),read(b[i].e),b[i].f=i;
sort(b+,b+m+,cmp);
for(i=;i<=n;i++)
if(!last[a[i]]){
last[a[i]]=i;
update(i);
}else{
next[last[a[i]]]=i;
last[a[i]]=i;
}
for(i=;i<=m;i++){
while(k<b[i].s){
if(next[k])update(next[k]);
k++;
}
ans[b[i].f]=query(b[i].e)-query(b[i].s-);
}
for(i=;i<=m;i++)printf("%d\n",ans[i]);
return ;
}
bzoj1878