【笔记】CDQ分治


Part 1 简介

CDQ分治,即基于时间的分治算法,最早被陈丹琦引入国内而得名。

Part 2 点对问题

  1. 找到这个序列的中点

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

    第一种是$1 ≤ i ≤ mid, 1 ≤ j ≤ mid$ 的点对

    第二种是$1 ≤ i ≤ mid, mid + 1 ≤ j ≤ n$ 的点对

    第三种是$mid + 1 ≤ i ≤ n, mid + 1 ≤ j ≤ n$ 的点对

  3. 将$(1, n)$ 这个序列拆成两个序列$(1, mid)$ 和$(mid + 1, n)$

    会发现第一类点对和第三类点对都在这两个序列之中,递归的去解决这两类点对

  4. 想方设法处理一下第二类点对的信息

Part 2.1 偏序问题

一维偏序直接sort

二维偏序第1维sort,第2维CDQ分治

三维偏序第1维sort,第2维CDQ分治,第3维数据结构

Part 2.1.1 二维偏序

有 $n$ 个元素,第 $i$ 个元素有 $a_i、b_i$ 两个属性,设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 的 $j$ 的数量。

对于 $d \in [0, n)$,求 $f(i) = d$ 的数量

我们可以把两个元素抽象成一个点 $(a,b)$, 那么我们就是求一个矩形中有多少个点。

首先我们可以按照 $x$ 轴 (a的值) 排个序,发现矩形右边的点已经不在答案的贡献里了。那么 $f(i)$ 就是在排序后的数组中找 $1\sim i-1$ 中有几个元素 $b$ 比 $b_i$ 小。

那么我们直接树状数组即可,时间复杂度 $O(n \log n)$

当我们插入一个 $b$ 值等于 $x$ 的点时,我们就令树状数组的 $x$ 位置单点 + 1,而查询数据结构里有多少个点小于 $x$ 的操作实际上就是在求前缀和

Part 2.1.2 三维偏序

有 $n$ 个元素,第 $i$ 个元素有 $a_i、b_i、c_i$ 三个属性,设 $f(i)$ 表示满足 $a_j \leq a_i$且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 的 $j$ 的数量。

对于 $d \in [0, n)$,求 $f(i) = d$ 的数量


Author: thyzzs
Reprint policy: All articles in this blog are used except for special statements CC BY-SA 4.0 reprint policy. If reproduced, please indicate source thyzzs !
  TOC