CDQ 分治 - 洛谷保存站

### 偏序问题

所谓偏序问题，就是给定一些元素，每个元素有一些初始值：$a_1 , a_2 , \cdots , a_n$，有时还会多加上几维，也就是还有 $b_1 , b_2 , \cdots , b_n$。

偏序问题，就是给定一些条件，比如规定必须 $a_i \le a_j , b_i \le b_j$，然后让我们求最长的子序列（或给定一些权值，求最大的子序列权值和，本质都是一样的）。

那么我们现在的经典模型就是只有一维，要你求序列中满足所有的 $i < j , a_i \le a_j$（也可以是小于），那么这就是一个最长不降（上升）子序列问题，也是一维偏序。

二维偏序就是多了一维，三维偏序就多了两维。

当我们在处理偏序问题时，我们通常有以下几个手段（按照难易度排序）：

- 排序

- 值域树状数组（需要离散化）

- 动态开点线段树

但是我们发现，排序固然好用，但是只能使用一次，而值域树状数组和动态开点线段树之间，我们必然会选择树状数组，因为其代码短，加上离散化也比线段树好写很多。

那么，我们要解决三维偏序问题时，是不是只能排序套树套树了呢？（三维线段树也不是不行）

这时候，我们就要引入我们今天的主角：CDQ 分治。

我们先从一维偏序入手，我们可以定义当前处理的区间为 $[l , r]$，区间的中点设为 $m$。

那么当前区间的贡献就可以由 $[l , m]$ 的内部贡献，$[m + 1 , r]$ 的内部贡献，以及由 $[l , m]$ 给 $[m + 1 , r]$ 的贡献组成，这是一个经典的分治模型。

那么，我们要处理好由左半区间给右半区间的贡献，我们可以使用归并排序。

上面这个过程中间，我们还可以使用树状数组来实现多处理一维，还可以用排序多处理一维。

那么我们在处理偏序问题时，算法考虑的优先级也呼之欲出了：

1. 排序

2. CDQ 分治

3. 值域树状数组

4. 动态开点线段树

好，那么我们引入今天的第一道例题：

### [Luogu - P3810](https://www.luogu.com.cn/problem/P3810)

因为题目中的点（也就是元素）会有重复，所以我们需要先去重。

这题是一个三维偏序的模板题，我们优先采用排序（以第一维为第一关键字，第二维为第二关键字，第三维为第三关键字，方便后续处理）给第一维处理掉，接下来用 CDQ 分治来处理剩下两维。

我们定义第四维为当前的点重复出现的数量，第五维为两个区间合并的贡献。

我们先递归处理两边的区间，然后开始双指针加归并排序：先让 $i$ 从 $l$ 枚举到 $r$，定义 $j$ 为左区间到了第几个，$k$ 为右区间到了第几个。

如果此时 $j$ 的第二维小于等于 $k$ 的第二维，且 $j$ 没有全部枚举完；或者此时的 $k$ 已经枚举完了，我们就需要将 $j$ 添加，同时在树状数组中插入第三维，数量即为这个点重复的数量。

如果此时需要添加右区间（即不满足上述条件），那么我们就将 $k$ 添加，因为此时是右区间，所以是左区间贡献给它，我们就要将 $k$ 的第五维，也就是答案统计 $k$ 的第二维出现了多少次，用树状数组查询即可。

最后的答案就是当前点的答案加上出现的次数减一（减去自己）的位置要加上自己出现的数量。

最后全部枚举完了以后，我们还要将树状数组清空！！！还要将归并完了的数组重新赋值回来！！！

其它的没什么好说的，去重和树状数组应该是基础操作。

```cpp line-numbers
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e5 + 1;

int n, n2, k0, ans[kMaxN], t[kMaxN];  // n2为去重后的长度，k0为题目中给定的值域范围，ans统计答案，t为树状数组
array<int, 5> a[kMaxN], a2[kMaxN];    // a为存储状态的，a2为归并时使用的数组

void A(int x, int v) {  // 树状数组插入
  for (; x <= k0; x += x & -x) {
    t[x] += v;
  }
}

int Q(int x) {  // 树状数组查询
  int s = 0;
  for (; x; x -= x & -x) {
    s += t[x];
  }
  return s;
}

void S(int l, int r) {  // CDQ分治
  if (l == r) {         // 如果只剩一个点了，就不处理
    return;
  }
  int m = l + r >> 1;                               // 区间的中点
  S(l, m), S(m + 1, r);                             // 先处理子区间
  for (int i = l, j = l, k = m + 1; i <= r; i++) {  // 归并
    if (k > r || j <= m && a[j][1] <= a[k][1]) {    // 如果第二维满足要求
      A(a[j][2], a[j][3]);                          // 添加
      a2[i] = a[j++];                               // 归并
    } else {                                        // 不满足
      a[k][4] += Q(a[k][2]);                        // 查询
      a2[i] = a[k++];                               // 归并
    }
  }
  for (int i = l; i <= m; i++) {
    A(a[i][2], -a[i][3]);  // 清空
  }
  copy(a2 + l, a2 + r + 1, a + l);  // 复制过来
}

int main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> n >> k0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i][0] >> a[i][1] >> a[i][2];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    if (a[i][0] != a[i - 1][0] || a[i][1] != a[i - 1][1] || a[i][2] != a[i - 1][2]) {  // 去重
      a[++n2] = a[i];
    }
    a[n2][3]++;
  }
  S(1, n2);
  for (int i = 1; i <= n2; i++) {
    ans[a[i][4] + a[i][3] - 1] += a[i][3];  // 统计答案
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
```

### 复杂度分析

分治是 $O(n \log n)$，树状数组是 $O(n \log k)$，总体时间复杂度 $O(n \log n \log k)$，也可以理解为 $O(n \log^2 n)$（对值进行离散化）。

空间是 $O(nv)$，其中 $v$ 是状态的数量，是个小常数。

### [Luogu - P3769](https://www.luogu.com.cn/problem/P3769)

这题看上去和上一题差不多，但是多了一维。

那么，我们就还是考虑先排序，然后 CDQ 分治。

这时要处理的区间就变成了一个平面，我们的第一层 CDQ 分治相当于给这个平面竖着砍了一刀，现在我们又要套上一层 CDQ 分治，给这个平面再横着砍一刀。

因为外面的分治是一维的，所以不需要在外面就使用树状数组。

那么，我们就可以使用第一层的分治来确定哪些点是进行贡献，哪些点是统计贡献。

那么，我们在第二层分治时，就先排序，然后分治左区间，然后再进行排序（两次排序的规则不同），接着跑双指针，这里不需要归并排序了，因为我们可以一起放外面。

跑完之后，还是要进行清空，最后再分治右区间。

这题的值域较大，需要离散化。

总结一下思路：首先排序解决第一维，然后对第二维进行 CDQ 分治求解贡献以及统计，然后再用一层 CDQ 分治解决第三维（根据第二维的贡献和统计进行计算），最后一维使用数据结构维护。

时间复杂度为 $O(n \log^3 n)$。

```cpp line-numbers
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 5e4 + 1;

array<int, 6> a[kMaxN], ord;  // ord为排序的关键字，方便处理
map<int, int> m;              // 离散化的map
int n, ans, t[kMaxN], dv;     // dv为离散化的编号

bool com(const array<int, 6>& x, const array<int, 6>& y) {  // 比较函数
  for (int i = 0; i < 6; i++) {
    if (x[ord[i]] != y[ord[i]]) {
      return x[ord[i]] < y[ord[i]];
    }
  }
  return false;
}

void A(int x, int v) {  // 插入
  for (; x <= dv; x += x & -x) {
    t[x] = v ? max(t[x], v) : 0;  // 树状数组要改为求最大值
  }
}

int Q(int x) {  // 查询
  int m = 0;
  for (; x; x -= x & -x) {
    m = max(m, t[x]);
  }
  return m;
}

void S(int l, int r) {  // 第二层CDQ
  if (l == r) {
    return;
  }
  ord = {1, 5, 2, 3, 4}, sort(a + l, a + r + 1, com);                                   // 以第一维为第一关键字，标记为第二关键字，先处理左边的区间
  int m = l + r >> 1;                                                                   // 中点
  S(l, m);                                                                              // 分治左区间
  ord = {2, 1, 5, 3, 4}, sort(a + l, a + m + 1, com), sort(a + m + 1, a + r + 1, com);  // 更改排序方式，对两个子区间分别排序（排序方式应该都能看懂）
  for (int i = l, j = m + 1; i <= m || j <= r;) {                                       // 双指针求解
    if (j > r || i <= m && a[i][2] <= a[j][2]) {                                        // 第三维满足条件
      if (!a[i][5]) {                                                                   // 当前的点是贡献
        A(a[i][3], a[i][4]);
      }
      i++;
    } else {
      if (a[j][5]) {                             // 当前的点是统计
        a[j][4] = max(a[j][4], Q(a[j][3]) + 1);  // 这题本质上是一个LIS（就是偏序），但是我们采用了分治的方式解决这个LIS
      }
      j++;
    }
  }
  for (int i = l; i <= m; i++) {
    A(a[i][3], 0);  // 清空
  }
  S(m + 1, r);
}

void S0(int l, int r) {  // 第一层CDQ
  if (l == r) {
    return;
  }
  int m = l + r >> 1;
  S0(l, m);
  for (int i = l; i <= r; i++) {
    a[i][5] = i > m;  // 计算标记（右区间统计答案，左区间进行贡献）
  }
  S(l, r);
  ord = {0, 1, 2, 3, 4}, sort(a + l, a + r + 1, com);  // 排序
  S0(m + 1, r);
}

int main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    m[a[i][3]] = 0, a[i][4] = 1;
  }
  for (auto& i : m) {
    i.second = ++dv;  // 离散化
  }
  for (int i = 1; i <= n; i++) {
    a[i][3] = m[a[i][3]];  // 离散化
  }
  ord = {0, 1, 2, 3, 4}, sort(a + 1, a + n + 1, com);  // 总体排序
  S0(1, n);
  for (int i = 1; i <= n; i++) {
    ans = max(ans, a[i][4]);  // 统计最大值
  }
  cout << ans;
  return 0;
}
```

再送一个双倍经验（求 LIS 时加上的东西变了）：[Luogu - P5621](https://www.luogu.com.cn/problem/P5621)

:::warning[注意！]
如果维度过多，那么你的时间复杂度会变为 $O(n \log^v n)$，其中 $v$ 是维度减一，则算法会的时间甚至不如 $O(n^2)$ 暴力 DP！
:::

### The End.

正在渲染内容...