P3810 三维偏序（陌上花开）

阅读量：

引子

cdq 分治究竟指的是什么呢？实际上，它是一种处理问题的思路，而非特定的算法（这一点与动态规划 dp 类似）。正因如此，cdq 分治所适用的场景非常广泛。由于这一思想最早由陈丹琦引入国内，因此被称作 cdq 分治。

关于 cdq 分治这一思路的延伸应用非常多样，但这些被称为 cdq 相关的内容在实现方式和核心原理上存在差异。不过，大致可以将其归类为以下三种类型：

1. 利用 cdq 分治解决与点对相关的问题

2. 通过 cdq 分治优化 1D/1D 动态规划中的状态转移过程

3. 借助 cdq 分治的思想，将某些动态问题转化为静态问题

这类问题通常会提供一个长度为 n 的序列，然后要求统计满足特定条件的点对 $(i,j)$ 的数量，或者是寻找使得某个函数取得最大值的点对 $(i,j)$ 之类的问题。

cdq 分治正是基于这样一种算法流程来应对这一类问题。

1. 确定该序列的中点 $mid$

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

**第一类为满足 $1 \leq i \leq mid,1 \leq j \leq m

还没有任何评论哟~