hdu 3333(树状数组)

题意：给出长度为n的数字序列，然后有q次询问，每次给出l r问区间[l, r]不同数字的和。

题解：因为询问次数有100000，可以离线处理，把所有询问存起来按右边界从小到大排序，这样再处理每个询问，最开始从位置1开始，从当前位置到他的右区间内，如果当前数字未被访问过，就把这个数字加入，如果已经访问过，就把之前位置加过的数字减掉，从当前位置再加入，这样就能保证询问区间内每个数字只被加一次。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define ll long long
using namespace std;
const int N = ;
const int M = ;
struct Query {
    int l, r, id;
}qu[M];
int n, q, a[N];
ll C[N], ans[M];
map<int, int> mp;

int cmp(Query a, Query b) {
    if (a.r == b.r)
        return a.l < b.l;
    return a.r < b.r;
}

int lowbit(int x) {
    return x & (-x);
}

ll Sum(int x) {
    ll res = ;
    while (x) {
        res += C[x];
        x -= lowbit(x);
    }
    return res;
}

void Add(int x, ll y) {
    while (x <= n) {
        C[x] += y;  
        x += lowbit(x);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        mp.clear();
        memset(C, , sizeof(C));
        scanf("%d", &n);
        for (int i = ; i <= n; i++)
            scanf("%d", &a[i]);
        scanf("%d", &q);
        for (int i = ; i < q; i++) {
            scanf("%d%d", &qu[i].l, &qu[i].r);
            qu[i].id = i;
        }
        sort(qu, qu + q, cmp);
        int cur = ;
        for (int i = ; i < q; i++) {
            for (; cur <= qu[i].r; cur++) {
                if (mp[a[cur]])
                    Add(mp[a[cur]], -a[cur]);
                mp[a[cur]] = cur;
                Add(cur, a[cur]);
            }
            ans[qu[i].id] = Sum(qu[i].r) - Sum(qu[i].l - );
        }
        for (int i = ; i < q; i++)
            printf("%lld\n", ans[i]);
    }
    return ;
}