三维偏序问题

解题思路

本题求的是一个三维偏序，是 CDQ 分治的模板题。然后本题问的还和三维偏序不太一样，因此答案需要特殊处理一下。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
    //a, b, c 表示权值，s 表示当前元素出现的次数，res 表示和当前元素配对的数的个数
    int a, b, c, s, res;
    bool operator< (const Data &t) const //按照三关键字排序
    {
        if(a != t.a) return a < t.a;
        if(b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data &t) const //重载等号
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N]; //存储所有三维元素，w 为归并排序的辅助数组
int tr[M], res[N]; //tr 表示树状数组，res 表示答案

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

void add(int x, int c) //树状数组：令 x 加上 c
{
    for(int i = x; i < M; i += lowbit(i)) tr[i] += c;
}

int query(int x) //树状数组：求 1 ~ x 的前缀和
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void merge_sort(int l, int r) //将所有元素按照第二关键字进行归并排序
{
    if(l >= r) return;

    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r); //归并左、右区间

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
        if(q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k++] = q[i++]; //如果 q[i].b <= q[j].b，i++
        else q[j].res += query(q[j].c), w[k++] = q[j++]; //此时 q[i].b 是第一个 > q[j].b 的数，更新 j 的答案
    while(i <= mid) add(q[i].c, q[i].s), w[k++] = q[i++]; //i 继续后移
    while(j <= r) q[j].res += query(q[j].c), w[k++] = q[j++]; //j 继续后移
    for(i = l; i <= mid; i++) add(q[i].c, -q[i].s); //重置树状数组
    for(i = l, j = 0; j < k; i++, j++) q[i] = w[j]; //将排好序的数组放会原数组
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }

    sort(q, q + n); //将所有元素按照三关键字排序

    //手动判重，并记录每个元素出现多少次
    int k = 1;
    for(int i = 1; i < n; i++)
        if(q[i] == q[k - 1]) q[k - 1].s++;
        else q[k++] = q[i];

    merge_sort(0, k - 1); //CDQ 分治

    for(int i = 0; i < k; i++) res[q[i].res += q[i].s - 1] += q[i].s; //处理答案
    for(int i = 0; i < n; i++) printf("%d\n", res[i]); //输出答案

    return 0;
}