SPOJ DQUERY树状数组离线or主席树

时间：2021-12-10 00:50:56
Time Limit: 227MS   Memory Limit: 1572864KB   64bit IO Format: %lld & %llu

Submit Status

Description

English Vietnamese

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

树状数组的方法：

/*

SPOJ DQUERY(hdu3333)线段树or树状数组离线

查询区间内不同数的个数

本来是学习主席树的，发现这方法不会也就写了下，感觉很机智

先将所有查询按区间右端从小到大排序，如果一个数已经出现过就先把以前位置上的删

掉然后在新的位置上插入，像这样在[l,r]中重复的就只计算了一次

hhh-2016-02-18 14:47:11

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef long long ll;

typedef long double ld;

int tot;

map<int , int >mp;

const int maxn = 100010;

int n;

int a[maxn],ans[maxn*2];

int s[maxn];

struct node

{

    int l,r,id;

} qu[maxn*2];

bool cmp(node a,node b)

{

    return a.r < b.r;

}

int lowbit(int x)

{

    return x&(-x);

}

void add(int x,int val)

{

    for(int i = x ; i <= n; i+=lowbit(i))

        s[i] += val;

}

int query(int x)

{

    int sum = 0;

    for(int i = x; i > 0; i -= lowbit(i))

        sum += s[i];

    return sum;

}

int main()

{

    while(scanf("%d",&n) != EOF)

    {

        mp.clear();

        memset(s,0,sizeof(s));

        for(int i =1 ; i <= n; i++)

            scanf("%d",&a[i]);

        int q;

        scanf("%d",&q);

        for(int i = 1; i <= q; i++)

        {

            scanf("%d%d",&qu[i].l,&qu[i].r);

            qu[i].id = i;

        }

        sort(qu+1,qu+q+1,cmp);

        int t = 1;

        for(int i= 1;i <= q;i++)

        {

            for(;t <= qu[i].r;t++)

            {

                if(mp[a[t]] != 0) add(mp[a[t]],-1);

                mp[a[t]] = t;

                add(t,1);

            }

            ans[qu[i].id] = query(qu[i].r) - query(qu[i].l-1);

        }

        for(int i = 1;i <= q;i++)

        {

            printf("%d\n",ans[i]);

        }

    }

    return 0;

}

主席树：  //参考：关于主席树的读书笔记

将1-i用线段树处理，每个表示前i个数的情况。如果每棵线段都建完整的话肯定会mle，我们发现对于前缀[1,i]和前缀[1,i+1]的线段树，如果b[i+1]<=mid (b[i+1]表示a[i+1]离散后的标记) 那么线段树i和线段树i+1的左边是完全相同的，根本不需要在建，只需要用指针指一下就好

//忘了在(=@__@=)哪里看的了

换一种解释，如果我们要修改左子树，那么右子树上的与上一个线段树相比不会变化，只需要指一下就好

/*

主席树 SPOJ DQUERY

查询区间有多少个不同的数。类似于之前树状数组离线的思路，在插入之前先进行判断

如果已经有了，把以前的先删掉再进行插入

hhh-2016-02-18 15:37:48

*/

#include <functional>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <map>

#include <cmath>

using namespace std;

typedef long long ll;

typedef long double ld;

using namespace std;

const int maxn = 100010;

int tot;

int n;

int a[maxn],t[maxn];

int T[maxn],lson[maxn*30],rson[maxn*30],c[maxn*30];

int build(int l,int r)

{

    int root = tot++;

    c[root] = 0;

    if(l != r)

    {

        int mid = (l+r)>>1;

        lson[root] = build(l,mid);

        rson[root] = build(mid+1,r);

    }

    return root;

}

//如果那里发生改变则兴建一个节点而非像平常修改那个节点的值

int update(int root,int pos,int val)

{

    int newroot = tot++;

    int tmp = newroot;

    c[newroot] = c[root] + val;

    int l = 1,r = n;

    while(l < r)

    {

        int mid = (l+r)>>1;

        if(pos <= mid)

        {

            lson[newroot] = tot++;

            rson[newroot] = rson[root];

            newroot = lson[newroot];

            root = lson[root];

            r = mid;

        }

        else

        {

            lson[newroot] = lson[root];

            rson[newroot] = tot++;

            newroot = rson[newroot];

            root = rson[root];

            l = mid+1;

        }

        c[newroot] = c[root] + val;

    }

    return tmp;

}

int query(int root,int pos)

{

    int l = 1, r = n;

    int ans = 0;

    while(pos > l)

    {

        int mid = (l+r)>>1;

        if(pos <= mid)

        {

            ans += c[rson[root]];

            r = mid;

            root = lson[root];

        }

        else

        {

            l = mid+1;

            root = rson[root];

        }

    }

    return ans+c[root];

}

int main()

{

    while(scanf("%d",&n) !=EOF)

    {

        tot = 0;

        map<int,int> mp;

        for(int i = 1; i <= n; i++)

            scanf("%d",&a[i]);

        T[0] = build(1,n);

        for(int i =1; i <= n; i++)

        {

            if(mp.find(a[i]) == mp.end())

                T[i] = update(T[i-1],i,1);

            else

            {

                int tt = update(T[i-1],mp[a[i]],-1);

                T[i] = update(tt,i,1);

            }

            mp[a[i]] = i;

        }

        int q;

        scanf("%d",&q);

        while(q--)

        {

            int l,r;

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

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

        }

    }

    return 0;

}

　　

相关文章