HDU - 5618 CDQ分治 + 树状数组

题意：

思路：

代码：

#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 10;const int MAXC = 1e5 + 10;const int MAXQ = MAXN;int maxc;struct BIT {    int C[MAXC];    int lowbit(int x) {        return x & -x;    }    void add(int x, int y) {        while (x <= MAXC) {            C[x] += y;            x += lowbit(x);        }    }    int sum(int x) {        int res = 0;        while (x) {            res += C[x];            x -= lowbit(x);        }        return res;    }     void clr(int x){         while (x <= MAXC) {             if (C[x]) C[x] = 0; else break;             x += lowbit(x);          }     }}bit;struct Query {    int id, b, c;    bool Operator < (const Query &rhs) const {        return b == rhs.b ? c <= rhs.c : b < rhs.b;    // 优先级一定要考虑到等于的情况    }}que[MAXQ], tmp[MAXQ];int ans[MAXN];void cdq(int l, int r) {    if (r - l <= 1) return;    int m = (l + r) >> 1;    cdq(l, m); cdq(m, r);    int p = l, q = m, cnt = 0;    while (p < m && q < r) {        if (que[p] < que[q]) {            bit.add(que[p].c, 1);            tmp[cnt++] = que[p++];        }        else {            ans[que[q].id] += bit.sum(que[q].c);            tmp[cnt++] = que[q++];        }    }    while (p < m) tmp[cnt++] = que[p++];    while (q < r) {        ans[que[q].id] += bit.sum(que[q].c);        tmp[cnt++] = que[q++];    }    for (int i = 0; i < cnt; i++) {        bit.clr(tmp[i].c);        que[i + l] = tmp[i];    }}struct node {    int id, a, b, c;    bool operator < (const node &rhs) const {        return a == rhs.a ? (b == rhs.b ? c < rhs.c : b < rhs.b) : a < rhs.a;   // 考虑位置因素，要按照先a再b后c的优先级排序    }}arr[MAXN];int main() {    //freopen("in.txt", "r", stdin);    int T;    scanf("%d", &T);    while (T--) {        int n;        scanf("%d", &n);        for (int i = 0; i < n; i++) {            scanf("%d%d%d", &arr[i].a, &arr[i].b, &arr[i].c);            arr[i].id = i;        }        sort (arr, arr + n);        maxc = 0;        for (int i = 0; i < n; i++) {            que[i] = (Query) {arr[i].id, arr[i].b, arr[i].c};            maxc = max(maxc, arr[i].c);        }        memset(ans, 0, sizeof(ans));        cdq(0, n);        for (int i = n - 1; i >= 0; i--) {            if (arr[i].a == arr[i + 1].a && arr[i].b == arr[i + 1].b && arr[i].c == arr[i + 1].c)                ans[arr[i].id] = ans[arr[i + 1].id];        // 倒着更新相同有序对的答案        }        for (int i = 0; i < n; i++)            PRintf("%d/n", ans[i]);    }    return 0;}