CDQ 分治

本页面将介绍 CDQ 分治。

简介

CDQ 分治是一种思想而不是具体的算法，与动态规划类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：

解决和点对有关的问题。
1D 动态规划的优化与转移。
通过 CDQ 分治，将一些动态问题转化为静态问题。

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。[^ref1]

解决和点对有关的问题

这类问题多数类似于「给定一个长度为 n 的序列，统计有一些特性的点对 $(i, j)$ 的数量/找到一对点 $(i, j)$ 使得一些函数的值最大」。

CDQ 分治解决这类问题的算法流程如下：

找到这个序列的中点 $m i d$ ；
将所有点对 $(i, j)$ 划分为 3 类：
1. $1 \leq i \leq m i d, 1 \leq j \leq m i d$ 的点对；
2. $1 \leq i \leq m i d, m i d + 1 \leq j \leq n$ 的点对；
3. $m i d + 1 \leq i \leq n, m i d + 1 \leq j \leq n$ 的点对。
将 $(1, n)$ 这个序列拆成两个序列 $(1, m i d)$ 和 $(m i d + 1, n)$ 。此时第一类点对和第三类点对都在这两个序列之中；
递归地处理这两类点对；
设法处理第二类点对。

可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。

在实际应用时，我们通常使用一个函数 solve(l,r) 处理 $l \leq i \leq r, l \leq j \leq r$ 的点对。上述算法流程中的递归部分便是通过 solve(l,mid) 与 solve(mid,r) 来实现的。剩下的第二类点对则需要额外设计算法解决。

例题

三维偏序

给定一个序列，每个点有 $a_{i}, b_{i}, c_{i}$ 三个属性，试求：这个序列里有多少对点对 $(i, j)$ 满足 $a_{j} \leq a_{i}$ 且 $b_{j} \leq b_{i}$ 且 $c_{j} \leq c_{i}$ 且 $j \neq i$ 。

解题思路

三维偏序是 CDQ 分治的经典问题。

题目要求统计序列里点对的个数，那试一下用 CDQ 分治。

首先将序列按 $a$ 排序。

假设我们现在写好了 solve(l,r)，并且通过递归搞定了 solve(l,mid) 和 solve(mid+1,r)。现在我们要做的，就是统计满足 $l \leq i \leq m i d$ , $m i d + 1 \leq j \leq r$ 的点对 $(i, j)$ 中，有多个点对还满足 $a_{i} < a_{j}$ , $b_{i} < b_{j}$ , $c_{i} < c_{j}$ 的限制条件。

稍微思考一下就会发现，那个 $a_{i} < a_{j}$ 的限制条件没啥用了：已经将序列按 $a$ 排序，则 $a_{i} < a_{j}$ 可转化为 $i < j$ 。既然 $i$ 比 $m i d$ 小， $j$ 比 $m i d$ 大，那 $i$ 肯定比 $j$ 要小。现在还剩下两个限制条件： $b_{i} < b_{j}$ 与 $c_{i} < c_{j}$ , 根据这个限制条件我们就可以枚举 $j$ , 求出有多少个满足条件的 $i$ 。

为了方便枚举，我们把 $(l, m i d)$ 和 $(m i d + 1, r)$ 中的点全部按照 $b$ 的值从小到大排个序。之后我们依次枚举每一个 $j$ , 把所有 $b_{i} < b_{j}$ 的点 $i$ 全部插入到某种数据结构里（这里我们选择树状数组）。此时只要查询树状数组里有多少个点的 $c$ 值是小于 $c_{j}$ 的，我们就求出了对于这个点 $j$ ，有多少个 $i$ 可以合法匹配它了。

当我们插入一个 $c$ 值等于 $x$ 的点时，我们就令树状数组的 $x$ 这个位置单点 + 1，而查询树状数组里有多少个点小于 $x$ 的操作实际上就是在求前缀和，只要我们事先对于所有的 $c$ 值做了离散化，我们的复杂度就是对的。

对于每一个 $j$ ，我们都需要将所有 $b_{i} < b_{j}$ 的点 $i$ 插入树状数组中。由于所有的 $i$ 和 $j$ 都已事先按照 $b$ 值排好序，这样的话只要以双指针的方式在树状数组里插入点，则对树状数组的插入操作就能从 $O (n^{2})$ 次降到 $O (n)$ 次。

通过这样一个算法流程，我们就用 $O (n \log n)$ 的时间处理完了关于第二类点对的信息了。此时算法的时间复杂度是 $T (n) = T (⌊ \frac{n}{2} ⌋) + T (⌈ \frac{n}{2} ⌉) + O (n \log n) = O (n \log^{2} n)$ 。

示例代码

#include <algorithm>
#include <iostream>

constexpr int MAXN = 1e5 + 10;
constexpr int MAXK = 2e5 + 10;

int n, k;

struct Element {
  int a, b, c;
  int cnt;
  int res;

  bool operator!=(Element other) const {
    if (a != other.a) return true;
    if (b != other.b) return true;
    if (c != other.c) return true;
    return false;
  }
};

Element e[MAXN];
Element ue[MAXN];
int m, t;
int res[MAXN];

struct BinaryIndexedTree {
  int node[MAXK];

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

  void Add(int pos, int val) {
    while (pos <= k) {
      node[pos] += val;
      pos += lowbit(pos);
    }
    return;
  }

  int Ask(int pos) {
    int res = 0;
    while (pos) {
      res += node[pos];
      pos -= lowbit(pos);
    }
    return res;
  }
} BIT;

bool cmpA(Element x, Element y) {
  if (x.a != y.a) return x.a < y.a;
  if (x.b != y.b) return x.b < y.b;
  return x.c < y.c;
}

bool cmpB(Element x, Element y) {
  if (x.b != y.b) return x.b < y.b;
  return x.c < y.c;
}

void CDQ(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  std::sort(ue + l, ue + mid + 1, cmpB);
  std::sort(ue + mid + 1, ue + r + 1, cmpB);
  int i = l;
  int j = mid + 1;
  while (j <= r) {
    while (i <= mid && ue[i].b <= ue[j].b) {
      BIT.Add(ue[i].c, ue[i].cnt);
      i++;
    }
    ue[j].res += BIT.Ask(ue[j].c);
    j++;
  }
  for (int k = l; k < i; k++) BIT.Add(ue[k].c, -ue[k].cnt);
  return;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> e[i].a >> e[i].b >> e[i].c;
  std::sort(e + 1, e + n + 1, cmpA);
  for (int i = 1; i <= n; i++) {
    t++;
    if (e[i] != e[i + 1]) {
      m++;
      ue[m].a = e[i].a;
      ue[m].b = e[i].b;
      ue[m].c = e[i].c;
      ue[m].cnt = t;
      t = 0;
    }
  }
  CDQ(1, m);
  for (int i = 1; i <= m; i++) res[ue[i].res + ue[i].cnt - 1] += ue[i].cnt;
  for (int i = 0; i < n; i++) cout << res[i] << '\n';
  return 0;
}

CQOI2011 动态逆序对

对于序列 $a$ ，它的逆序对数定义为集合 ${(i, j) | i < j \land a_{i} > a_{j}}$ 中的元素个数。

现在给出 $1 \sim n$ 的一个排列，按照某种顺序依次删除 $m$ 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

示例代码

// 仔细推一下就是和三维偏序差不多的式子了，基本就是一个三维偏序的板子
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
int n;
int m;

struct treearray {
  int ta[200010];

  void ub(int& x) { x += x & (-x); }

  void db(int& x) { x -= x & (-x); }

  void c(int x, int t) {
    for (; x <= n + 1; ub(x)) ta[x] += t;
  }

  int sum(int x) {
    int r = 0;
    for (; x > 0; db(x)) r += ta[x];
    return r;
  }
} ta;

struct data_ {
  int val;
  int del;
  int ans;
} a[100010];

int rv[100010];
ll res;

// 重写两个比较
bool cmp1(const data_& a, const data_& b) { return a.val < b.val; }

bool cmp2(const data_& a, const data_& b) { return a.del < b.del; }

void solve(int l, int r) {  // 底下是具体的式子，套用
  if (r - l == 1) {
    return;
  }
  int mid = (l + r) / 2;
  solve(l, mid);
  solve(mid, r);
  int i = l + 1;
  int j = mid + 1;
  while (i <= mid) {
    while (a[i].val > a[j].val && j <= r) {
      ta.c(a[j].del, 1);
      j++;
    }
    a[i].ans += ta.sum(m + 1) - ta.sum(a[i].del);
    i++;
  }
  i = l + 1;
  j = mid + 1;
  while (i <= mid) {
    while (a[i].val > a[j].val && j <= r) {
      ta.c(a[j].del, -1);
      j++;
    }
    i++;
  }
  i = mid;
  j = r;
  while (j > mid) {
    while (a[j].val < a[i].val && i > l) {
      ta.c(a[i].del, 1);
      i--;
    }
    a[j].ans += ta.sum(m + 1) - ta.sum(a[j].del);
    j--;
  }
  i = mid;
  j = r;
  while (j > mid) {
    while (a[j].val < a[i].val && i > l) {
      ta.c(a[i].del, -1);
      i--;
    }
    j--;
  }
  sort(a + l + 1, a + r + 1, cmp1);
  return;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].val;
    rv[a[i].val] = i;
  }
  for (int i = 1; i <= m; i++) {
    int p;
    cin >> p;
    a[rv[p]].del = i;
  }
  for (int i = 1; i <= n; i++) {
    if (a[i].del == 0) a[i].del = m + 1;
  }
  for (int i = 1; i <= n; i++) {
    res += ta.sum(n + 1) - ta.sum(a[i].val);
    ta.c(a[i].val, 1);
  }
  for (int i = 1; i <= n; i++) {
    ta.c(a[i].val, -1);
  }
  solve(0, n);
  sort(a + 1, a + n + 1, cmp2);
  for (int i = 1; i <= m; i++) {
    cout << res << '\n';
    res -= a[i].ans;
  }
  return 0;
}

CDQ 分治

简介

解决和点对有关的问题

例题

CDQ 分治优化 1D/1D 动态规划的转移