rt。树状数组写法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+15;

int a[N],tr[N],n,m,ans[N];
bool vis[N];

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

void add(int k,int x){
    for(;k<=n;k+=lowbit(k)){
        tr[k]+=x;
    }
}

int sum(int k){
    int res=0;
    for(;k;k-=lowbit(k)){
        res+=tr[k];
    }
    return res;
}

struct node{
    int l,r,index;
}q[N];

bool cmp(node a,node b){
    return a.r<b.r;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    
    cin>>m;
    
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].index=i;
    }
    sort(q+1,q+m+1,cmp);
    
    int last=1;
    
    for(int i=1;i<=m;i++){
        for(int j=last;j<=q[i].r;j++){
            if(vis[a[j]]){
                add(vis[a[j]],-1);
            }
            add(j,1);
            vis[a[j]]=j;
        }
        last=q[i].r+1;
        ans[q[i].index]=sum(q[i].r)-sum(q[i].l-1);
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}