SPOJ-DQUERY-D-query(議長数、区間別要素個数)

題意:何度も区間の中で異なる要素の個数の構想を尋ねた:主席樹の入門問題、N本の線分樹を建てて、各記録区間[1,n]区間の中で各要素が最後に現れた位置.照会時に直接減算します.

#include 
#include 
using namespace std;
const int maxn=1e5+100;
int a[maxn],root[maxn],f[maxn],cur,lastnum[maxn];
struct node{
    int cnt,flag;
    int left,right;
}son[maxn*20];
void pushup(int x){
    son[x].cnt=son[son[x].right].cnt+son[son[x].left].cnt;
}
int build(int l,int r){
    int k=cur++;
    if(l==r){
        son[k].cnt=0;
        son[k].flag=0;
        return k;
    }
    int mid=(l+r)/2;
    son[k].left=build(l,mid);
    son[k].right=build(mid+1,r);
    pushup(k);
    return k;
}
int update(int x,int l,int r,int pos,int val){
    int k=cur++;
    son[k]=son[x];
    if(l==r){
        son[k].cnt+=val;
        return k;
    }
    int mid=(l+r)/2;
    if(pos<=mid) son[k].left=update(son[x].left,l,mid,pos,val);
    else son[k].right=update(son[x].right,mid+1,r,pos,val);
    pushup(k);
    return k;
}
int query(int a,int b,int l,int r,int x,int y){
    if(l>=x&&r<=y)return son[b].cnt-son[a].cnt;
    int mid=(l+r)/2;
    if(mid>=y)return query(son[a].left,son[b].left,l,mid,x,y);
    else if(midreturn query(son[a].right,son[b].right,mid+1,r,x,y);
    else return query(son[a].left,son[b].left,l,mid,x,mid)+query(son[a].right,son[b].right,mid+1,r,mid+1,y);
}
int main(){
    int n,m;
    cur=1;
    scanf("%d",&n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            f[i] = a[i];
        }
        int sum = 1;
        sort(f + 1, f + 1 + n);
        for (int i = 2; i <= n; i++) {//     
            if (f[i] != f[i - 1])f[++sum] = f[i];
        }
        int temproot=0;
        for (int i = 1; i <= n; i++) {//      ，             
            a[i] = lower_bound(f + 1, f + 1 + sum, a[i]) - f;
            if(!lastnum[a[i]]){//            ，                ，        
                root[i]=update(root[i-1],1,n,i,1);
            }else{
                temproot=update(root[i-1],1,n,lastnum[a[i]],-1);
                root[i]=update(temproot,1,n,i,1);
            }
            lastnum[a[i]]=i;
        }
        scanf("%d",&m);
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%d
",query(root[a-1],root[b],1,n,a,b));//    ，   [1，r]      [1,l-1]      
        }
    return 0;
}