题解：P3810 【模板】三维偏序（陌上花开）

complete_binary_tree · 2025-05-07 16:36:58 · 题解

本题解使用 CDQ 分治做法。

什么是 CDQ 分治？

CDQ 分治是由 2008 年 IOI 金牌得主陈丹琦在高中时整理并总结的一种分治思想^1，可以用于解决偏序问题、一些动规的优化、离线按时间顺序处理等。

CDQ 分治最经典的应用就是处理一些点对 (i,j)(i \le j)，此时它的主要思想如下：

1. 把序列从 mid 切开，分成两半；

2. 把点对分成三类：

   • 第一类是 j \le mid，即都在左半部分；

   • 第二类是 i > mid，即都在右半部分；

   • 最后一类是横跨 mid 的部分。

3. 左右两半分别递归，处理前两类点对。

4. 想办法处理最后一类点对。

以本题为例，本题是要找到一些点对满足偏序关系。

首先我们可以对第一维 a 进行排序，这样序列后面的数一定大于序列前面的数，我们就可以少处理一维。

接着，我们在处理第二维的时候进行 CDQ 分治。

对于一个 [l,r] 的区间，我们可以如此做：

• 首先先处理 [l,mid] 和 (mid,r]。（mid 是区间中点）

  • 如果 l=r，那么一定没有贡献，可以直接返回。

• 然后，我们处理左端点在 [l,mid]，右端点在 (mid,r] 的点对的贡献。

  • 由于我们已经按 a 排好序，所以右区间 (mid,r] 的点的 a 值一定大于左区间。

  • 此时我们把两个区间分别按照 b 排序。

  • 这样虽然会打乱区间内 a 的顺序，但是我们只考虑跨区间的贡献。而且区间内的贡献我们在前面已经算完了，后面只会算更大块区间的两侧贡献，而大块之间的 a 的顺序并不会被排序影响。

  • 然后我们用树状数组+双指针法处理 c 的偏序关系。

  • 由于我们只要算跨区间的贡献（b_i,c_i 都小于 b_j,c_j，且 i 在左区间、j 在右区间的点对 i,j 个数），所以树状数组上第 i 位存 c_x=i 的 x 在左区间出现了多少次。（需要离散化）

  • 我们两个指针 x,y 分别扫左区间和右区间。当 y 增加后，我们把满足 b_x \le b_y 的 c_x 都加入树状数组。由于 b 是有序的，所以可以用一个指针扫。等到所有满足条件的 c_x 都加入树状数组后，我们只需查询树状数组上 1 \sim c_y 的前缀和即是右端点为 y 的贡献。

• 然后我们退回上一层，继续这样操作，直到求出所有答案。

这就是本题的 CDQ 分治思路。

正确性 & 时间复杂度分析

由于我们开始对 a 排好了序，而我们是从下到上 CDQ 分治的，所以 a 这一维的偏序可以保证正确。

然后，我们对 b 进行排序，使用双指针确保加入树状数组的数的 b 值都小于要求贡献的数的 b 值。

最后，查询树状数组中的 1 \sim c_y 的前缀和，由于是把左区间的数加入树状数组，所以可以保证不重复。

时间复杂度：

• 离散化 & a 排序：O(n \log n)

• 对于 CDQ 分治：

  • b$ 排序 & 树状数组：$O(n \log n)

  • 总时间复杂度：T(n) = O(n \log n) + 2T(\frac n 2) = O(n \log^2 n)

所以时间复杂度是 O(n \log^2 n)。

常数优化

对 b 排序如果每次都用 sort，常数较大。我们发现因为我们在往下递归的时候完成了左右两部分的 b 的排序，所以我们在这层可以直接把这两部分归并，在排序部分做到 O(n)，这样总时间复杂度的第二个 \log 就只有树状数组的小常数 O(n \log n)。

实现细节

• 记得清空树状数组！！！ 不能使用暴力清空（时间复杂度会变成 O(n^2 \log n)），怎么加入的怎么清空（实在不理解你可以再来一遍双指针，但是不要再统计一遍答案）

• 要去重！！！ 重复的元素可以互相贡献，但是上述算法处理不了重复元素（只会算一次贡献）。去重后树状数组要加上这个元素的个数。

• 前面对 a 排序时 a 相等要对 b 排序，b 也相等要对 c 排序。CDQ 内对 b 排序，b 相等时可以不用对 c 排序。（请读者思考一下为什么[^2]）

• 还是不对？看看讨论区“警示后人”。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, A = 2e5 + 5;

struct node{
    int ans, gs;
    int a, b, c;
};

node a[N], b[N];
int n, _n, k, bowl[N];
long long ans[N];

// 对a排序 
bool cmp(node x, node y){
    // 注意a/b相等时的处理 
    if(x.a == y.a) 
        if(x.b == y.b) 
            return x.c < y.c;
        else
            return x.b < y.b;
    return x.a < y.a;
}
// cdq内对b排序 
bool cmp2(node x, node y){ 
    /*if(x.b == y.b)
        return x.c < y.c;*/
    // 上面这个if可要可不要 
    return x.b < y.b;
}

// 树状数组 
struct treez{
    int t[A];
    int find(int x){
        int ans = 0;
        for(; x; x -= (x & (-x))) ans += t[x];
        return ans;
    }
    void add(int x, int y){
        for(; x <= 2e5; x += (x & (-x))) t[x] += y;
    }
} tr;

//cdq主体 
void cdq(int l, int r){
    if(l == r) return ;
    int mid = (l + r) >> 1;

    // 1.递归左右 
    cdq(l, mid), cdq(mid + 1, r);

    // 2.排序 
    sort(a + l, a + mid + 1, cmp2), sort(a + mid + 1, a + r + 1, cmp2);

    // 3.双指针求贡献 
    int i = l, j = mid + 1;
    for(; j <= r; ++j){
        while(i <= mid && a[i].b <= a[j].b) tr.add(a[i].c, a[i].gs), i++;
        a[j].ans += tr.find(a[j].c);
    }

    // 4.清空树状数组 
    for(int k = l; k < i; ++k){
        tr.add(a[k].c, -a[k].gs);
    }
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d%d", &b[i].a, &b[i].b, &b[i].c);

    sort(b + 1, b + n + 1, cmp);

    // 神秘の去重 
    int w = 0;
    for(int i = 1; i <= n; ++i){
        ++w;
        if(b[i].a != b[i + 1].a || b[i].b != b[i + 1].b || b[i].c != b[i + 1].c){
            a[++_n] = b[i];
            a[_n].gs = w;
            w = 0;
        }
    }

    cdq(1, _n);

    // 相同数字可以重复贡献，别忘了加上 
    for(int i = 1; i <= _n; ++i) bowl[a[i].ans + a[i].gs - 1] += a[i].gs;

    for(int i = 0; i < n; ++i) printf("%d\n", bowl[i]);
    return 0;
}

[^2]: 前者可能导致 b(c) 更大的被分在左区间，而后者由于加入树状数组的先后顺序/查询的先后顺序没有影响，所以后者不在相等时排序 c 也是可以的。