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