【笔记】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$ 的数量


  转载请注明: thyzzs' Blog 【笔记】CDQ分治

 上一篇
【笔记】Knuth-Morris-Pratt 算法 【笔记】Knuth-Morris-Pratt 算法
Part 1 简介模式串匹配,就是给定一个需要处理的文本串(理论上应该很长)和一个需要在文本串中搜索的模式串(理论上长度应该远小于文本串),查询在该文本串中,给出的模式串的出现有无、次数、位置等。 Part 2 前缀函数给定一个长度为 $
2019-11-13
下一篇 
【笔记】珂朵莉树 【笔记】珂朵莉树
珂朵莉树(Chtholly Tree),又名老司机树(Old Driver Tree, ODT),是一种非常暴力的维护序列信息的数据结构。
2019-11-12
  目录