题意：长度为\(n\)的序列\(a\)，\(m\)个询问，每次询问\([l,r]\)中有多少种数。

题解：假设我们现在查询的区间是\([l,r]\)，这其中某个数字重复出现了，如果我们将询问离线储存下来，按右区间从小到大遍历的话，那么这个数字只要取区间中最后一次出现的位置就好。那么有了这个这个结论，我们就可以用前缀和来处理贡献了。

代码：

#include <bits/stdc++.h>

using namespace std;
const int N=1e6+10;
#define PII pair<int,int>
#define fi first
#define se second
int n,m;
int a[N];
int c[N];
int vis[N];
int ans[N];

struct Node{
    int x,y;
    int id;
}seg[N];

int lowbit(int x){
    return x&(-x);
}

void update(int i,int k){
    while(i<=1000010){
        c[i]+=k;
        i+=lowbit(i);
    }
}

int query(int i){
    int res=0;
    while(i){
        res+=c[i];
        i-=lowbit(i);
    }
    return res;
}

int main(){
    scanf("%d",&n);

    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }

    scanf("%d",&m);

    for(int i=1;i<=m;++i) {
        scanf("%d %d",&seg[i].x,&seg[i].y);
        seg[i].id=i;
    }
     
    sort(seg+1,seg+1+m,[&](Node a,Node b){
        return a.y<b.y;
    });

    int l=1;
    for(int i=1;i<=m;++i){
        for(int j=l;j<=seg[i].y;++j){
            if(vis[a[j]]) update(vis[a[j]],-1);
            update(j,1);
            vis[a[j]]=j;
        }
        l=seg[i].y+1;
        ans[seg[i].id]=query(seg[i].y)-query(seg[i].x-1);
    }
    
    for(int i=1;i<=m;++i){
        printf("%d\n",ans[i]);
    }
     
    return 0;
}