跳转至

CDQ 分治

本页面将介绍 CDQ 分治。

简介

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

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

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

解决和点对有关的问题

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

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

  1. 找到这个序列的中点 \(mid\)；

  2. 将所有点对 \((i,j)\) 划分为 3 类：

    1. \(1 \leq i \leq mid,1 \leq j \leq mid\) 的点对；
    2. \(1 \leq i \leq mid ,mid+1 \leq j \leq n\) 的点对；
    3. \(mid+1 \leq i \leq n,mid+1 \leq j \leq n\) 的点对。

  3. 将 \((1,n)\) 这个序列拆成两个序列 \((1,mid)\) 和 \((mid+1,n)\)。此时第一类点对和第三类点对都在这两个序列之中；

  4. 递归地处理这两类点对；

  5. 设法处理第二类点对。

可以看到 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 \ne i\)。

解题思路

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

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

首先将序列按 \(a\) 排序。

假设我们现在写好了 solve(l,r)，并且通过递归搞定了 solve(l,mid) 和 solve(mid+1,r)。现在我们要做的，就是统计满足 \(l \leq i \leq mid\),\(mid+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\) 比 \(mid\) 小，\(j\) 比 \(mid\) 大，那 \(i\) 肯定比 \(j\) 要小。现在还剩下两个限制条件：\(b_{i}<b_{j}\) 与 \(c_{i}<c_{j}\), 根据这个限制条件我们就可以枚举 \(j\), 求出有多少个满足条件的 \(i\)。

为了方便枚举，我们把 \((l,mid)\) 和 \((mid+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(\lfloor \frac{n}{2} \rfloor)+T(\lceil \frac{n}{2} \rceil)+O(n\log n)=O(n\log^2n)\)。

示例代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#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 \wedge a_i > a_j \}\) 中的元素个数。

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

示例代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// 仔细推一下就是和三维偏序差不多的式子了，基本就是一个三维偏序的板子
#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 分治优化 1D/1D 动态规划的转移

1D/1D 动态规划指的是一类特定的 DP 问题，该类题目的特征是 DP 数组是一维的，转移是 \(O(n)\) 的。如果条件良好的话，有时可以通过 CDQ 分治来把它们的时间复杂度由 \(O(n^2)\) 降至 \(O(n\log^2n)\)。

例如，给定一个序列，每个元素有两个属性 \(a\)，\(b\)。我们希望计算一个 DP 式子的值，它的转移方程如下：

$dp_{i}=1+ \max_{j=1}^{i-1}dp_{j}[a_{j}