[洛谷P3810]【模板】三维偏序（陌上花开）

题目大意：有$n$个元素，第$i$个元素有三个属性$a_i,b_i,c_i$，设$f(i)=\sum\limits_{i\not = j}[a_j\leqslant a_i,b_j\leqslant b_i,c_j\leqslant c_i]$，令$d(i)=\sum\limits_{j=1}^n[f(j)=i]$，求$d$

题解：三位偏序，我用了$CDQ$分治，$a$排序解决，$b$$CDQ$分治，$c$用树状数组

卡点：无

 

C++ Code：

#include <cstdio>
#include <algorithm>
#define maxn 100010
#define maxm 200010
int n, k, tot;
int d[maxn];
struct node {
    int a, b, c, cnt, f;
    inline bool operator == (const node &rhs) const {
        return (a == rhs.a && b == rhs.b && c == rhs.c);
    }
} v[maxn], s[maxn];
inline bool cmpb(node lhs, node rhs) {return lhs.b == rhs.b ? lhs.c < rhs.c : lhs.b < rhs.b;}
inline bool cmpa(node lhs, node rhs) {return lhs.a == rhs.a ? cmpb(lhs, rhs) : lhs.a < rhs.a;}
namespace Binary_Indexed_Tree {
    int Tr[maxm];
    int res;
    inline void add(int p, int num) {for (; p <= k; p += p & -p) Tr[p] += num;}
    inline int ask(int p) {res = 0; for (; p; p &= p - 1) res += Tr[p]; return res;}
}
using Binary_Indexed_Tree::add;
using Binary_Indexed_Tree::ask;
void CDQ(int l, int r) {
    if (l == r) return ;
    int mid = l + r >> 1;
    CDQ(l, mid); CDQ(mid + 1, r);
    std::sort(s + l, s + mid + 1, cmpb);
    std::sort(s + mid + 1, s + r + 1, cmpb);
    int pl = l, pr = mid + 1;
    while (pl <= mid && pr <= r) {
        if (s[pl].b <= s[pr].b) add(s[pl].c, s[pl].cnt), pl++;
        else s[pr].f += ask(s[pr].c), pr++;
    }
    while (pr <= r) s[pr].f += ask(s[pr].c), pr++;
    for (int i = l; i < pl; i++) add(s[i].c, -s[i].cnt);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &v[i].a, &v[i].b, &v[i].c);
    std::sort(v + 1, v + n + 1, cmpa);
    for (int i = 1, j; (j = i) <= n; i = j) {
        while (j <= n && v[i] == v[j]) j++;
        s[++tot] = v[i]; s[tot].cnt = j - i;
    }
    CDQ(1, tot);
    for (int i = 1; i <= tot; i++) d[s[i].f + s[i].cnt] += s[i].cnt;
    for (int i = 1; i <= n; i++) printf("%d\n", d[i]);
    return 0;
}