CDQ分治⚓︎

$\text{CDQ}$ 分治是通过将问题划分为更小的子问题来简化计算过程，并在合并结果时进行必要的调整。

$\text{CDQ}$ 分治通常用于解决一些需要处理大量数据的复杂问题，特别是在计算逆序对、二维平面上的点对计数等问题中。常见的应用包括：

点对计数问题
一维动态规划的优化
离线查询问题

逆序对⚓︎

逆序对是指在一个数组中，前面的元素大于后面的元素的情况。计算逆序对的数量是一个经典的问题，常用的解决方法包括归并排序和树状数组。

分治树状数组

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> nums(n);
  for (int i = 0; i < n; ++i) { cin >> nums[i]; }
  auto solve = [&](auto &&self, int low, int high) -> int64_t {
    if (low >= high) { return 0; }
    int mid = low + ((high - low) / 2);
    // 先递归计算左右子数组的逆序对数量
    int64_t count = self(self, low, mid) + self(self, mid + 1, high);
    vector<int> merge(high - low + 1);
    // 计算跨越左右子数组的逆序对数量并合并, 并且排序
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
      if (nums[i] <= nums[j]) {
        merge[k++] = nums[i++];
      } else {
        merge[k++]  = nums[j++];
        count      += mid - i + 1;  // 逆序对
      }
    }
    while (i <= mid) { merge[k++] = nums[i++]; }
    while (j <= high) { merge[k++] = nums[j++]; }
    for (int p = 0; p < merge.size(); ++p) { nums[low + p] = merge[p]; }
    return count;
  };

  int64_t ans = solve(solve, 0, n - 1);
  cout << ans << '\n';
  return 0;
}

通过离散化数组元素并使用树状数组进行频率统计，可以在 $O(n \log n)$ 的时间复杂度内完成计算。

线段树也可以实现类似的功能，但树状数组通常更为简洁和高效。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct BIT {
  explicit BIT(int64_t n) : n(n), tree(n + 1) {}

  void point_add(int64_t x, int64_t delta) {
    for (; x <= n; x += lowbit(x)) { tree[x] += delta; }
  }

  int64_t sum(int64_t x) {
    int64_t ret = 0;
    for (; x > 0; x -= lowbit(x)) { ret += tree[x]; }
    return ret;
  }

  int64_t range_sum(int64_t x, int64_t y) { return sum(y) - sum(x - 1); }

  static int64_t lowbit(int64_t x) { return x & (-x); }

  int64_t n;
  vector<int64_t> tree;
};

int main() {
  int n;
  cin >> n;
  vector<int> nums(n);
  for (int i = 0; i < n; ++i) { cin >> nums[i]; }
  vector<int> sorted_nums = nums;
  sort(sorted_nums.begin(), sorted_nums.end());

  auto get_rank = [&](int num) {
    return lower_bound(sorted_nums.begin(), sorted_nums.end(), num) - sorted_nums.begin() + 1;
  };

  int64_t ans = 0;
  BIT bit(n);
  for (int64_t i = n - 1; i >= 0; --i) {
    int rank  = get_rank(nums[i]);
    ans      += bit.range_sum(1, rank - 1);
    bit.point_add(rank, 1);
  }
  cout << ans << '\n';
  return 0;
}

点对计数⚓︎

类似归并排序的思路， $\text{CDQ}$ 分治将数组递归地划分为左右两部分，分别计算每部分的逆序对数量，然后在合并过程中计算跨越左右部分的逆序对数量。这样可以有效地减少计算量，提高效率。

$\text{CDQ}$ 分治解决点对计数问题的关键在于如何在合并过程中高效地计算跨越左右部分的点对数量。通常可以通过维护一个辅助数组来实现这一点。具体步骤如下：

将数组递归地划分为左右两部分，直到每部分只包含一个元素
点对 $(i,j)$ 可以划分为三类：
- 完全在左半部分的点对： $i,j \in [low, mid]$
- 完全在右半部分的点对： $i,j \in [mid+1, high]$
- 跨越左右两部分的点对： $i \in [low, mid], j \in [mid+1, high]$
递归计算左右两部分的点对数量
在合并过程中，使用双指针或其他数据结构（如树状数组）来高效地计算跨越左右部分的点对数量

【模板】三维偏序

有 $n$ 个点 $(a_i, b_i, c_i)$ ，统计每个点的支配点数量。点 $p_1$ 支配点 $p_2$ 当且仅当 $a_1 \leq a_2, b_1 \leq b_2, c_1 \leq c_2$ 。对于每个 $k$ ，输出有多少点的支配点数量为 $k$ 。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct BIT {
  explicit BIT(int64_t n) : n(n), tree(n + 1) {}

  void point_add(int64_t x, int64_t delta) {
    for (; x <= n; x += lowbit(x)) { tree[x] += delta; }
  }

  int64_t sum(int64_t x) {
    int64_t ret = 0;
    for (; x > 0; x -= lowbit(x)) { ret += tree[x]; }
    return ret;
  }

  static int64_t lowbit(int64_t x) { return x & (-x); }

  int64_t n;
  vector<int64_t> tree;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, k;
  cin >> n >> k;
  // (a, b, c, i), i 为原始下标
  vector<vector<int>> nums(n + 1, vector<int>(4, 0));
  vector<int> res(n + 1, 0);  // 记录每个点的支配点数量
  for (int i = 1; i <= n; i++) {
    cin >> nums[i][0] >> nums[i][1] >> nums[i][2];
    nums[i][3] = i;  // 记录原始下标
  }
  // 按照 a, b, c 三个维度排序
  sort(nums.begin() + 1, nums.end());
  auto equal = [&](int x, int y) {
    return nums[x][0] == nums[y][0] && nums[x][1] == nums[y][1] && nums[x][2] == nums[y][2];
  };
  for (int l = 1, r = 1; l <= n; l = r) {  // 处理相同点
    while (r <= n && equal(r, l)) { ++r; }
    for (int i = l; i < r; ++i) {      // 一组内前面的点在CDQ中不会计算它之后的点
      res[nums[i][3]] += (r - i - 1);  // 先加上相同点的数量
    }
  }

  BIT bit(k);
  auto merge = [&](int left, int mid, int right) {
    int j = left;
    for (int i = mid + 1; i <= right; ++i) {
      while (j <= mid && nums[j][1] <= nums[i][1]) {
        bit.point_add(nums[j][2], 1);
        ++j;
      }
      res[nums[i][3]] += bit.sum(nums[i][2]);
    }
    // 清空 BIT
    for (int i = left; i < j; ++i) { bit.point_add(nums[i][2], -1); }
    // 根据 b 维度排序
    sort(nums.begin() + left, nums.begin() + right + 1,
         [&](const vector<int> &a, const vector<int> &b) { return a[1] < b[1]; });
  };

  auto cdq = [&](auto &&self, int left, int right) -> void {
    if (left >= right) { return; }
    int mid = (left + right) / 2;
    self(self, left, mid);
    self(self, mid + 1, right);
    merge(left, mid, right);
  };

  cdq(cdq, 1, n);

  vector<int64_t> answer(n, 0);
  for (int i = 1; i <= n; ++i) { ++answer[res[i]]; }
  for (int i = 0; i < n; ++i) { cout << answer[i] << "\n"; }
  return 0;
}

Range Knapsack Query

有 $n$ 件物品和 $q$ 个查询。每件物品有一个重量 $w_i$ 和一个价值 $v_i$ 。每个查询给出三个整数 $(l, r, c)$ ，表示在区间 $[l, r]$ 内选择若干物品放入容量为 $c$ 的背包中，求能获得的最大价值。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <tuple>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> weight(n + 1), value(n + 1);
  for (int i = 1; i <= n; i++) { cin >> weight[i] >> value[i]; }
  int q;
  cin >> q;
  vector<tuple<int, int, int>> query;
  int max_c = 0;
  for (int i = 0; i < q; i++) {
    int l, r, c;
    cin >> l >> r >> c;
    query.emplace_back(l, r, c);
    max_c = max(max_c, c);
  }

  auto update = [&](const vector<int64_t> &pre, vector<int64_t> &next, int i) {
    for (int j = 0; j <= max_c; j++) {
      next[j] = pre[j];
      if (j >= weight[i]) { next[j] = max(next[j], pre[j - weight[i]] + value[i]); }
    }
  };

  vector dp(n + 1, vector<int64_t>(max_c + 1));
  vector<int64_t> ans(q);
  auto cdq = [&](auto &&cdq, int l, int r, const vector<int> &qid) -> void {
    if (l == r) {          // 只有一个物品
      for (int i : qid) {  // 此时必须有 ql == l && qr == r
        auto [ql, qr, c] = query[i];
        ans[i]           = (c >= weight[l] ? value[l] : 0);  // 能否放得下
      }
      return;
    }
    int m = (l + r) / 2;                  // 划分为 [l, m] 和 [m+1, r]
    fill(dp[m].begin(), dp[m].end(), 0);  // 初始化中点状态
    // 计算右半部分状态, 从中点向右推进, dp[i](m < i <= r) 表示 [m+1, i]
    // 物品的最优解
    for (int i = m + 1; i <= r; i++) { update(dp[i - 1], dp[i], i); }
    // 计算左半部分状态, 从中点向左推进, dp[i](l <= i <= m) 表示 [i, m]
    // 物品的最优解
    for (int j = weight[m]; j <= max_c; j++) { dp[m][j] = value[m]; }
    for (int i = m - 1; i >= l; i--) { update(dp[i + 1], dp[i], i); }
    // 分配查询
    vector<int> qid_l, qid_r;
    for (int i : qid) {
      auto [ql, qr, c] = query[i];
      if (qr <= m) {  // 全在左部分
        qid_l.push_back(i);
      } else if (ql > m) {  // 全在右部分
        qid_r.push_back(i);
      } else {  // 横跨两部分, 需要合并左右部分状态, 从左边选 j 个容量, 右边选
                // c-j 个容量
        for (int j = 0; j <= c; j++) { ans[i] = max(ans[i], dp[ql][j] + dp[qr][c - j]); }
      }
    }
    cdq(cdq, l, m, qid_l);
    cdq(cdq, m + 1, r, qid_r);
  };
  vector<int> qid(q);  // query ids
  iota(qid.begin(), qid.end(), 0);
  cdq(cdq, 1, n, qid);
  for (int i = 0; i < q; i++) { cout << ans[i] << '\n'; }
  return 0;
}

CDQ分治⚓︎

逆序对⚓︎

点对计数⚓︎

评论