一、CDQ 分治
因为时间的关系，我也不确定我理解的这个套路是否是所谓的 “CDQ 分治”，还是只是一种具有二维偏序特征的模板。
在这种题目中，我们一般会对于一个二维结构体去排序，比如说
struct Node
{
int x;
int y;
};而且排序一般会发生两次，第一次是在开始前先对某个维度进行一遍排序，然后在分治过程中，利用归并排序的思想，在二分的过程中对于另一个维度再次进行排序。也就是如下模板
struct Node
{
int x;
int y;
};
// 处理数组
Node a[MAXN];
bool cmp_x(const Node &a, const Node &b)
{
return a.x < b.x;
}
bool cmp_y(const Node &a, const Node &b)
{
return a.y < b.y;
}
void rec(int left, int right)
{
// 边界条件的处理，也可能是其他的
if (left == right)
{
return;
}
int mid = (left + right) >> 1;
rec(left, mid);
rec(mid + 1, right);
// 利用此时 [left, mid], [mid + 1, right] 已经相对于 y 有序的性质，进行一些操作
// process
// .....
// inplace_merge 是 std 里的一个方法，他会将有序的 [left, mid) 和 [mid, right) 数组合并成有序的 [left, right) 数组，同时不需要用临时数组
inplace_merge(a + left, a + mid + 1, a + right + 1, cmp_y);
}
int main()
{
// input a
sort(a + left, a + right + 1, sort_x);
rec(left, right);
}按照 CDQ 分支的标准定义，它是“每一次划分出来的两个子问题，前一个子问题用来解决后一个子问题，而不是其本身”，这个说法就比较的费解，不过考虑到二分的性质，所有的“后一个问题”就可以组成问题的全体，所以也不是太难理解。
至于为什么前一个问题可以解决后一个问题，我觉得它这里是侧重于两点，一个是在 rec 的操作过程中（就是注释的部分），经常遍历 [mid + 1, right] 这个区间上的元素，同时每次都考虑的是该区间上的元素与 [left, mid] 前面这个区间上全体元素的作用。那么具体利用的性质有两点：
[mid + 1, right]上的所有元素都相对于[left, mid]上的元素在x维上有序，这是第一次排序导致的。[left, mid]上的元素是相对于y维有序的，这是第二次排序导致的。
我们利用第一条性质确定了作用关系，也就是说，因为右侧元素在 x 维上一定比左侧元素大，所以我们可以进行一定的处理。，第二条性质确定了作用方式，也就是说，因为左侧元素是有序的，所以我们无论是查找还是累加还是贪心，都是很方便的。
在算法运行的过程中，会发现原本相对于 x 有序的数组，逐渐变成了相对于 y 有序的数组，但是因为分治“一层层”进行的特性，所以即使有序性逐渐丧失和重构，也会在母问题中保证对于 x 的有序性，在子问题中保证低于 y 的有序性。
在复杂性分析方面，因为 merge 是 $O(n)$ 的，所以只要 process 的过程是一个复杂度不超过 $O(n^2)$ 的过程，这要求对于右侧每个元素的处理时间复杂度要小于 $O(n)$ ，也就意味着基本上要利用到有序的性质，那么就可以达到优化的目的。
首先看求解逆序数的题目
逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
输入格式
第一行，一个数 $n$，表示序列中有 $n$个数。
第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。
输出格式
输出序列中逆序对的数目。
样例 #1
样例输入 #1
6 5 4 2 6 3 1样例输出 #1
11提示
对于 $25\%$ 的数据，$n \leq 2500$
对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。
对于所有数据，$n \leq 5 \times 10^5$
这道题的答案如下
#include <cstdio>
#include <iostream>
using namespace std;
int n, a[500010], c[500010];
long long ans;
void rec(int left, int right)
{
if (left == right)
return;
int mid = (left + right) / 2, i = left, j = mid + 1, k = left;
rec(left, mid), rec(mid + 1, right);
// 这里将 process 和 merge 的过程融合到了一起
while (i <= mid && j <= right)
if (a[i] <= a[j])
{
c[k++] = a[i++];
}
else
{
c[k++] = a[j++];
// 统计答案，利用的是 [left, mid] 的有序性，所以可以直接计算出在 [left, mid] 中大于 a[j] 的元素的个数
ans += mid - i + 1;
}
while (i <= mid)
c[k++] = a[i++];
while (j <= right)
c[k++] = a[j++];
for (int l = left; l <= right; l++)
a[l] = c[l];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
rec(1, n);
printf("%lld", ans);
return 0;
}这道题有一些相对于模板的变异：
- 没有对第一维进行排序：这是因为本质上第一维就是数组下标
index，所以一定是已经排序好的。 merge和process是混合在一起的：这是因为是可以混合在一起的，其实分开也可以。
那么这道题是如何利用二次排序的性质的呢？我们首先回顾逆序数的定义
所以有
- 第一次排序（实际上没有排序）保证了右侧区间的
index一定是大于左侧区间的index的，所以也就是一定有i < j（如果i在左侧区间，j在右侧区间），所以我们的下一步就是找到a[i] > a[j]的个数（固定j）。 - 如果一个个遍历左侧区间去获得
a[i] > a[j]的个数，那么是不可以的，因为此时这样对于每个右侧元素的时间复杂度就变成了 $O(n)$ ，但是幸亏保证了左侧区间是是有序的，所以我们可以直接利用一个指针进行计算（也就是a[j + 1]一定比a[j]的逆序数对数多或者相等 ）。
然后看平面最小点对，这个题目严格意义上并不是 CDQ 分治
平面上的最接近点对
题目描述
给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的。
输入格式
第一行一个整数 $n$，表示点的个数。
接下来 $n$ 行，每行两个整数 $x,y$ ，表示一个点的行坐标和列坐标。
输出格式
仅一行，一个实数，表示最短距离，四舍五入保留 $4$ 位小数。
样例 #1
样例输入 #1
3 1 1 1 2 2 2样例输出 #1
1.0000提示
数据规模与约定
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4$，$0 \leq x, y \leq 10^9$，小数点后的数字个数不超过 $6$。
题解如下
#include <bits/stdc++.h>
using namespace std;
struct Point
{
double x;
double y;
};
const int MAXN = 1e4 + 5;
Point p[MAXN];
int n;
double min_dist = 1e20;
inline void update_ans(const Point &a, const Point &b)
{
double dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
// cout << "dist: " << dist << endl;
if (min_dist > dist)
{
min_dist = dist;
}
}
bool cmp_x(const Point &a, const Point &b)
{
if (a.x == b.x)
{
return a.y < b.y;
}
else
{
return a.x < b.x;
}
}
bool cmp_y(const Point &a, const Point &b)
{
if (a.y == b.y)
{
return a.x < b.x;
}
else
{
return a.y < b.y;
}
}
void rec(int left, int right)
{
// 基准情况，当区间缩小为 3 的时候，进行逐一比较，至于为啥不到 2 ，我也不清楚
if (right - left <= 3)
{
for (int i = left; i <= right; i++)
{
for (int j = i + 1; j <= right; j++)
{
update_ans(p[i], p[j]);
}
}
// 对于 [left, right] 区间进行按照 y 轴的排序
sort(p + left, p + right + 1, cmp_y);
return;
}
int mid = (left + right) >> 1;
// 在分治前需要记录相对于 x 轴排序的 mid 的中点的 x 坐标，用于在中线处比较
double mid_x = p[mid].x;
// 进行分治，分治的结果是 [left, mid], [mid + 1, right] 两个区间的点都按照 y 轴排序
rec(left, mid);
rec(mid + 1, right);
// inplace_merge 表示一种就地的 merge 行为，即将 [left, mid), [mid, right) 两个序列整合成 [left, right) 的有序序列
// 这种 merge 本来应该是需要临时数组的，但是 inplace_merge 并不需要
// 经过 merge 后 [left, right) 都是按照 y 轴排列的了
inplace_merge(p + left, p + mid + 1, p + right + 1, cmp_y);
// 这个 vector 中存储着所有的离 mid 近的点
vector<Point> near;
// 遍历所有的点，填写 near，更新答案
for (int i = left; i <= right; i++)
{
// 这是满足进入 near 的条件，新的 min_dist 有可能在 near 中产生
if (abs(p[i].x - mid_x) < min_dist)
{
// 遍历已有的 near，让 p[i] 与 near 相比较，near 一定是 y 升序的
for (int j = near.size() - 1; j >= 0 && p[i].y - near[j].y < min_dist; j--)
{
update_ans(near[j], p[i]);
}
// 填充 near
near.push_back(p[i]);
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> p[i].x >> p[i].y;
}
sort(p, p + n, cmp_x);
rec(0, n - 1);
printf("%.4lf", min_dist);
return 0;
}这个题目十分符合两次排序的特征：
- 第一次排序对于
x轴进行，这样使得点可以被划分成左右两侧。 - 第二次排序对于
y轴进行，并且是在分治过程中完成的。
但是这道题的答案并不是利用左区间的性质解决右区间得出来的，但是依然利用了两次排序的性质：
- 根据第一次排序的结果，我们找到了
x轴中线的位置，这样才方便结束了对于两个子问题的二分后，讨论中线附近依然可能存在最小点对的可能。 - 我们是先进行
merge，然后进行处理，也就是说，处理的时候[left, right]已经是一个关于y轴有序的数组了，此时我们再进行遍历，可以利用有序性简化near数组间的比较（看上去应该是一个 $O(n)$ 的时间，实际上 $O(1)$ 就可以完成）。
下面一道题可以说是 CDQ 分治的板子题，如下所示
[USACO04OPEN] MooFest G
题目描述
约翰的 $n$ 头奶牛每年都会参加“哞哞大会”。
哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。
它们参加活动时会聚在一起，第 $i$ 头奶牛的坐标为 $x_i$，没有两头奶牛的坐标是相同的。
奶牛们的叫声很大，第 $i$ 头和第 $j$ 头奶牛交流，会发出
$\max{v_i,v_j}\times |x_i − x_j |$
的音量，其中 $v_i$ 和 $v_j$ 分别是第 $i$ 头和第 $j$ 头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。
输入格式
第一行：单个整数 $n$，$1\le n\le2\times 10^4$
第二行到第 $n + 1$ 行：第 $i + 1$ 行有两个整数 $v_i$ 和 $x_i$（$1\le v_i,x_i\le2\times 10^4$）。
输出格式
单个整数：表示所有奶牛产生的音量之和
样例 #1
样例输入 #1
4 3 1 2 5 2 6 4 3样例输出 #1
57
其题解如下
#include <bits/stdc++.h>
using namespace std;
struct Cow
{
int x;
int v;
};
const int MAXN = 1e5 + 5;
Cow a[MAXN], tmp[MAXN];
int n;
long long ans;
bool cmp(const Cow &a, const Cow &b)
{
return a.v < b.v;
}
bool cmp_x(const Cow &a, const Cow &b)
{
return a.x < b.x;
}
void CDQ(int left, int right)
{
if (left >= right)
{
return;
}
int mid = (left + right) >> 1;
CDQ(left, mid);
CDQ(mid + 1, right);
long long s1 = 0, s2 = 0;
// 此时 s1 是 [left, mid] 的 x 的和
for (int i = left; i <= mid; i++)
{
s1 += a[i].x;
}
int cur = left;
// 遍历右侧区间，计算右侧区间每个元素对左侧区间所有元素的声音
// 对于右侧的每个元素 a[i]，其公式为：
// a[i].x * cnt1 - s2 - a[i].x * cnt2 + s1
// cnt1 是左侧区间中小于 a[i].x 的元素的个数
// cnt2 是左侧区间中大于 a[i].x 的元素的个数
// s1 是左侧区间中小于 a[i].x 的元素的和
// s2 是左侧区间中大于 a[i].x 的元素的和
// 至于为啥要这样计算，是因为可以避免遍历
// 计算利用了左右侧区间的 x 升序特性
for (int i = mid + 1; i <= right; i++)
{
// cur 是左侧区间的一个分界线，其左侧都是小于 a[i].x
while (cur <= mid && a[cur].x < a[i].x)
{
s2 += a[cur].x;
s1 -= a[cur].x;
cur++;
}
long long cnt1 = cur - left;
long long cnt2 = mid - cur + 1;
ans += ((cnt1 * a[i].x - s2) + (-cnt2 * a[i].x + s1)) * a[i].v;
}
// 进行归并排序
inplace_merge(a + left, a + mid + 1, a + right + 1, cmp_x);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i].v >> a[i].x;
}
sort(a, a + n, cmp);
CDQ(0, n - 1);
cout << ans;
return 0;
}这道题属于是，无论是 $max(v_i, v_j)$ 还是 $\vert x_i - x_j \vert$ 都在暗示，必须将枚举 $(i, j)$ 对，才可以解决这个问题，但是实际上，我们可以利用两次排序，避免枚举：
- 首先对于
v进行排序 - 然后在分治过程中，对于
x进行排序。
我们是这样利用性质的（设 i 为左区间元素，j 为右区间元素）：
- 因为右区间的
v一定是大于左区间的v的，所以 $max(v_i, v_j) = v_j$ ，所以我们可以考虑对于每一个j，其左区间上是如何的（可以合并同类项了） - 因为左区间在
x上是有序的，所以对于 $\vert x_i - x_j \vert$ 这个问题，当固定j的时候，一定存在一个cur使得当i < cur的时候，$x_i < x_j$ ，当i > cur的时候，$x_i > x_j$ ，那么就可以将绝对值去掉了，并且不再是加法而改成了乘法。