「算法笔记」CDQ 分治

$\text{CDQ}$ 分治是我们处理各类问题的重要武器。它的优势在于可以顶替复杂的高级数据结构,而且常数比较小;缺点在于必须离线操作。


概述

$\text{CDQ}$ 分治一般用于离线处理一系列操作,这些操作一般包括修改和询问。它通过递归计算子问题、计算两部分的贡献来高效地处理问题。


基本思想

  1. 我们把操作看做一个序列,用区间 $[l,r]$ 表示。将这个区间 $[l,r]$ 分成两部分 $[l,m],[m+1,r]$。
  2. 。递归处理左右区间的操作。
  3. 。合并两个子问题,同时考虑左区间 $[l,m]$ 对右区间 $[m+1,r]$ 的贡献。即用左区间帮助解决右区间的问题。

$\text{CDQ}$ 分治和一般分治的主要不同在于:普通分治在合并子问题时,左区间不会对右区间产生影响。


偏序问题

给定一个序列 $a_i$,每个数有 $k$ 个属性,其中第 $i$ 的数的属性为 $(x_{i,1},x_{i,2},\cdots,x_{i,k})$。称 $a_i>a_j$ 当且仅当对于任意整数 $l\in[1,k]$ 都有 $x_{i,l}>x_{j,l}$。求对于序列中的每个元素 $a_i$,比 $a_i$ 小的元素个数。

三维偏序

题目链接:「LOJ 112」三维偏序

我们将每个数的属性用 $(x_i,y_i,z_i)$ 表示。首先把序列按照 $x_i$ 排序,接下来把第二维 $y_i$ 利用 $\text{CDQ}$ 分治递归计算子问题。合并时按照 $y_i$ 归并排序,用树状数组维护 $z_i​$,左区间更新右区间的答案即可。注意要及时把树状数组归零。

时间复杂度:$\mathcal O(n\log^2 n)$

四维偏序

题目链接:NULL

比三维多了一维?那么再套一个 $\text{CDQ}$ 不就行了?QAQ

时间复杂度:$\mathcal O(n\log^3 n)$

更高维偏序

题目链接:NULL

对于更更高维的偏序问题,虽然可以继续套 $\text{CDQ}$ 分治,这样的复杂度在渐进意义下是优秀的,但是在 $n$ 比较小的情况下还没有暴力跑得快。

我们可以使用对于每一维,用 $\text{bitset}$ 记录前面比当前数小的元素集合,最后把 $\text{bitset}$ 取个 $\&​$ 即可。

使用分块降低复杂度。

时间复杂度:$\mathcal O(kn\sqrt n)$,其中 $k$ 为维数。


总结

对于多维偏序问题、多维数据结构问题,我们可以用一步步降维。例如排序、数据结构、$\text{CDQ}$ 分治等都是降维工具。

我们还可以利用 $\text{CDQ}$ 分治加速动态规划等,具体应用可以参考下方习题。


习题

1 条评论

  1. realSpongeBob

    $$ \texttt{QwQ} $$

发表评论