【题意】维护一个区间不同的数的个数。

【解题方法】首先我们把所有查询区间记录下来，然后按照区间的右值排序，接着从左到右把每一个数更新到线段树中，并记录它出现的位置。如果一个数已经出现过，那么我们就把他上次出现的位置的值置为0，并更新它出现的位置。因为我们的查询区间是按右值排序的，因此把过去重复出现的数字置为0不会影响结果。当更新到某个区间的右值时，我们就查询一次该区间的答案，并把答案记下来。最后把区间查询的答案按照输入顺序输出即可。这样复杂度就成了nlogn。

【AC 代码】

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn=100010;
int n,m,a[maxn];
map<int,int>vis;
struct Q{
    int l,r,id;
    bool operator<(const Q &rhs)const{
        return r<rhs.r;
    }
}q[maxn];
ll ans[maxn];
struct node{
    int l,r;
    ll sum;
}Tree[maxn<<2];
void pushup(int rt)
{
    Tree[rt].sum=Tree[rt*2].sum+Tree[rt*2+1].sum;
}
void Build(int l,int r,int rt)
{
    Tree[rt].l=l,Tree[rt].r=r,Tree[rt].sum=0 ;
    if(l==r){
        return ;
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update(int pos,int val,int rt)
{
    if(Tree[rt].l==Tree[rt].r){
        Tree[rt].sum+=(ll)val;
        return ;
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(pos<=mid) update(pos,val,rt*2);
    else update(pos,val,rt*2+1);
    pushup(rt);
}
ll queryans(int L,int R,int rt)
{
    if(L==Tree[rt].l&&Tree[rt].r==R){
        return Tree[rt].sum;
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
//    ll ret=0;
//    if(L<=mid) ret+=queryans(L,mid,rt*2);
//    if(mid<R)  ret+=queryans(mid+1,R,rt*2+1);
//    return ret;
    if(R<=mid) return queryans(L,R,rt*2);
    else if(L>mid) return queryans(L,R,rt*2+1);
    else{
        return queryans(L,mid,rt*2)+queryans(mid+1,R,rt*2+1);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        vis.clear();
        memset(ans,0,sizeof(ans));
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        scanf("%d",&m);
        for(int i=1; i<=m; i++){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q+1,q+m+1);
        Build(1,n,1);
        //puts("success");
        int now=1;
        for(int i=1; i<=m; i++){
            for(;now<=q[i].r;now++){
                if(vis[a[now]]) update(vis[a[now]],-1,1);
                update(now,1,1);
                vis[a[now]]=now;
            }
            ans[q[i].id]=queryans(q[i].l,q[i].r,1);
        }
        for(int i=1; i<=m; i++) printf("%lld\n",ans[i]);
    }
}