HDU Ads Proposal 【树状数组】

题意：N个customer，M个advertisement，每个ad只属于一个cus，每个ad都有一个点击量和一个长度值。现在对于每个询问，求出所有cus的前k大点击量的广告的总长度。

对于每个ad，求出他在所属的cus里面的排名，这个一边排序就可以了。

将长度累加到对应排名上面。树状数组维护查询就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 500010
ll s[N];
int n, m, q;

struct node {
    int u, c, l;
    bool operator<(const node&x ) const {
        return (u<x.u) || (u==x.u && c>x.c);
    }
} a[N];
inline int lowbit(int x) { return x & (-x); }
void add(int x, ll y) {
    while (x <= m) {
        s[x] += y;
        x += lowbit(x);
    }
}
ll sum(int x) {
    ll ret = 0;
    while (x) {
        ret += s[x];
        x -= lowbit(x);
    }
    return ret;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    int T;
    scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        scanf("%d%d%d", &n, &m, &q);
        for (int i=0; i<m; i++)
            scanf("%d%d%d", &a[i].u, &a[i].c, &a[i].l);
        sort(a, a+m);
        memset(s, 0, sizeof(s));
        int last = 0;
        for (int i=0; i<m; i++) {
            if (a[i].u != a[last].u) last = i;
            add(i-last+1, (ll)a[i].l);
        }
        printf("Case #%d:\n", cas);
        int k;
        while (q--) {
            scanf("%d", &k);
            if (k > m) k = m;
            printf("%I64d\n", sum(k));
        }
    }

    return 0;
}