bzoj1878-[SDOI2009]HH的项链(树状数组)

[SDOI2009]HH的项链

1.思路

　　题目的意思就是给一个 序列,然后多个询问,对于每个询问,给出一个区间,让你求出这个区间的不同元素的个数,此类问题目前我所知道有三种方法:

　　　　(1).主席树

　　　　(2).莫队算法

　　　　(3).树状数组,假定我们要处理的数组为a,首先我们将所有的询问区间按左端点从小到大排序;然后用个数组b,将数组a中的每个数第一次出现的位置pos, b[pos]=1,然后保存一个指针li,代表当前我们所处理的位置,当li<当前询问区间l时,我们将a[li]在li后出现的第一个位置处pos标记,b[pos]=1, 然后对于当前询问区间的答案就是b[l]+b[l+1] .... + b[r], 为了便于修改和查询,可以用个树状数组来维护这个值.

2.代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+5;
struct Query{
    int l, r, id;
    bool operator < (const Query &a) const {
        return l < a.l;
    }
};

Query q[N*4];
int head[N*20];
int np[N];
int a[N];
int s[N];
int res[N*4];

void add(int i, int v) {
    while(i < N) {
        s[i] += v;
        i += i&(-i);
    }
}

int getSum(int i) {
    int res = 0;
    while(i > 0) {
        res += s[i];
        i -= i&-i;
    }
    return res;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        memset(head, 0, sizeof(head));
        memset(s, 0, sizeof(s));
        for(int i = 1; i <= n; ++ i) {
           scanf("%d", &a[i])
            if(!head[a[i]]) {
                add(i, 1);
                head[a[i]] = -1;
            }
        }


        for(int i = n; i; -- i) {
            np[i] = head[a[i]];    // np[i]代表a[i]在i之后出现的第一个位置
            head[a[i]] = i;
        }

        int m;
        scanf("%d", &m)
        for(int i = 0; i < m; ++ i) {
            scanf("%d%d", &q[i].l, &q[i].r);
            q[i].id = i;
        }

        sort(q, q+m);

        int l = 1;
        for(int i = 0; i < m; ++ i) {
            while(l < q[i].l) {
                if(np[l]!=-1) {
                    add(np[l], 1);   // 将a[l]出现的下一个位置+1
                }
                ++ l;
            }
            res[q[i].id] = getSum(q[i].r) - getSum(q[i].l-1);
        }

        for(int i = 0; i < m; ++ i) {
            printf("%d
", res[i]);
        }
    }
    return 0;
}