SPOJ 3267 DQUERY - D-query （主席树）（区间数的种数）

た入场券 2022-01-06 08:43 188阅读 0赞

## DQUERY - D-query ##

[\#sorting][sorting] [\#tree][tree]

<table style="border-spacing:0px;border-collapse:collapse;"> 
 <tbody> 
  <tr> 
   <td><a style="color:#337ab7;text-decoration:none;" href="http://www.spoj.com/problems/DQUERY/en/" rel="nofollow">English</a></td> 
   <td><a style="color:#337ab7;text-decoration:none;" href="http://www.spoj.com/problems/DQUERY/vn/" rel="nofollow">Vietnamese</a></td> 
  </tr> 
 </tbody> 
</table>

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

### Input ###

*  Line 1: n (1 ≤ n ≤ 30000).
 *  Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106). 
 *  Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
 *  In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

### Output ###

*  For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

### Example ###

Input
    5
    1 1 2 1 3
    3
    1 5
    2 4
    3 5
    
    Output
    3
    2
    3

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <time.h>
    #include <string>
    #include <map>
    #include <stack>
    #include <vector>
    #include <set>
    #include <queue>
    #define met(a,b) memset(a,b,sizeof a)
    #define pb push_back
    #define lson(x) ((x<<1))
    #define rson(x) ((x<<1)+1)
    using namespace std;
    typedef long long ll;
    const int N=5e4+50;
    const int M=N*N+10;
    struct seg {
        int lson,rson;
        int cnt;
    };
    seg T[N*20];
    int root[N],tot;
    vector<int>pos;
    int arr[N];
    int last_pos[N];
    
    void init() {
        pos.clear();
        met(root,0);met(last_pos,0);
        tot=0;
        T[0].cnt=T[0].lson=T[0].rson=0;
    }
    void update(int &cur,int ori,int l,int r,int pos,int flag) {
        cur=++tot;
        T[cur]=T[ori];
        T[cur].cnt+=flag;
        if(l==r)
            return ;
        int mid=(l+r)/2;
        if(pos<=mid)
            update(T[cur].lson,T[ori].lson,l,mid,pos,flag);
        else
            update(T[cur].rson,T[ori].rson,mid+1,r,pos,flag);
    }
    int query(int S,int E,int l,int r,int x,int y) {
        if(x<=l&&r<=y)
            return T[E].cnt-T[S].cnt;
        else {
            int mid=(l+r)/2;
            if(y<=mid)
                return query(T[S].lson,T[E].lson,l,mid,x,y);
            else if(x>mid)
                return query(T[S].rson,T[E].rson,mid+1,r,x,y);
            else
                return query(T[S].lson,T[E].lson,l,mid,x,mid)+query(T[S].rson,T[E].rson,mid+1,r,mid+1,y);
        }
    }
    int main(void) {
        int n,m,i,l,r;
        while (~scanf("%d",&n)) {
            init();
            for (i=1; i<=n; ++i) {
                scanf("%d",&arr[i]);
                pos.push_back(arr[i]);
            }
            scanf("%d",&m);
            sort(pos.begin(),pos.end());
            pos.erase(unique(pos.begin(),pos.end()),pos.end());
            int temp_rt=0;
            for (i=1; i<=n; ++i) {
                arr[i]=lower_bound(pos.begin(),pos.end(),arr[i])-pos.begin()+1;
                if(!last_pos[arr[i]]) {
                    update(root[i],root[i-1],1,n,i,1);
                    last_pos[arr[i]]=i;
                } else {
                    update(temp_rt,root[i-1],1,n,last_pos[arr[i]],-1);
                    update(root[i],temp_rt,1,n,i,1);
                    last_pos[arr[i]]=i;
                }
            }
            for (i=0; i<m; ++i) {
                scanf("%d%d",&l,&r);
                printf("%d\n",query(root[l-1],root[r],1,n,l,r));
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/jianrenfang/p/6372294.html

[sorting]: http://www.spoj.com/problems/tag/sorting
[tree]: http://www.spoj.com/problems/tag/tree