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

DQUERY - D-query

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+;

const int M=N*N+;

struct seg {

    int lson,rson;

    int cnt;

};

seg T[N*];

int root[N],tot;

vector<int>pos;

int arr[N];

int last_pos[N];

void init() {

    pos.clear();

    met(root,);met(last_pos,);

    tot=;

    T[].cnt=T[].lson=T[].rson=;

}

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)/;

    if(pos<=mid)

        update(T[cur].lson,T[ori].lson,l,mid,pos,flag);

    else

        update(T[cur].rson,T[ori].rson,mid+,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)/;

        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+,r,x,y);

        else

            return query(T[S].lson,T[E].lson,l,mid,x,mid)+query(T[S].rson,T[E].rson,mid+,r,mid+,y);

    }

}

int main(void) {

    int n,m,i,l,r;

    while (~scanf("%d",&n)) {

        init();

        for (i=; 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=;

        for (i=; i<=n; ++i) {

            arr[i]=lower_bound(pos.begin(),pos.end(),arr[i])-pos.begin()+;

            if(!last_pos[arr[i]]) {

                update(root[i],root[i-],,n,i,);

                last_pos[arr[i]]=i;

            } else {

                update(temp_rt,root[i-],,n,last_pos[arr[i]],-);

                update(root[i],temp_rt,,n,i,);

                last_pos[arr[i]]=i;

            }

        }

        for (i=; i<m; ++i) {

            scanf("%d%d",&l,&r);

            printf("%d\n",query(root[l-],root[r],,n,l,r));

        }

    }

    return ;

}

巴特西

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

DQUERY - D-query

Input

Output

Example

最新文章

热门文章