例题：
P7883 平面最近点对（加强加强版） - 洛谷
P5094 MooFest G 加强版 - 洛谷
P3810 【模板】三维偏序（陌上花开） - 洛谷
核心思想：
CDQ分治是一种将高维问题不断降维处理的离线分治算法，主要用于计算“一侧”
对“另一侧”的贡献；
可用于处理多维偏序问题、不支持在线查询但允许离线处理的动态问题;
分治步骤：
不妨假设为三维偏序问题X、Y、Z
- Step 1：降维-排序
- 首先对第一维X进行排序，若X相同则按Y排序，以此类推；
- 这确保了在下一步的分治过程中左侧的第一维一定小于右侧；
- Step 2：分治
- 定义递归函数
cdq( l, r ); - 递归跳出条件
l >= r - 中点
mid = l + ((r - l) >> 1); - 递归左半部分
cdq(l, mid) - 递归右半部分
cdq(mid+1, r)
- 定义递归函数
- Step 3：计算左侧对右侧的贡献、合并两侧
- 二维问题，可以使用双指针和数据结构（如树状数组或线段树）解决
- 将
[l, mid]和[mid + 1, r]两个子区间内的点按第二维 X 排序。 - 使用两个指针，i 遍历右区间的点，j 遍历左区间的点。
- 对于每个右区间的点 \(P_i\)，我们将所有满足条件的左区间点 \(P_j\) 的第三维 \(P_j.z\) 加入到一个以 z 为下标的树状数组中。
- 然后，查询树状数组中下标小于等于 \(P_i.z\) 的值的总和，这个总和就是左区间对 \(P_i\) 的贡献。将这个贡献累加到 \(P_i\) 的答案中。
实现细节与注意事项
- 去重： 如果存在完全相同的点 \((x,y,z)\)，在排序和计算时需要特别处理，否则可能导致重复计算。一个常见的技巧是先对所有点去重，并记录每个点的出现次数。
- 归并排序的妙用： 在计算贡献的步骤中，如果使用归并排序来对 b 维进行排序，可以省去每次都调用
sort的开销，将这一步的复杂度从 \(O(nlogn)\) 优化到 \(O(n)\)，从而使整体算法的结构更清晰。 - 数据结构的选择： 树状数组因其代码简短、常数小，是处理第三维时的首选。
- 离散化： 如果 y 或 z 的值域很大，需要先进行离散化。
题解：
P3810 【模板】三维偏序（陌上花开） - 洛谷
思路与分治步骤相同，时间复杂度\(O(nlog^2n)\)#include <bits/stdc++.h> using namespace std; #define int long long #define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)// 快读 template <typename T> inline T read() {T x = 0; bool neg = false; char ch = getchar();while (!isdigit(ch)) { if (ch == '-') neg = true; ch = getchar(); }while (isdigit(ch)) { x = x * 10 + (ch ^ 48); ch = getchar(); }return neg ? -x : x; }// 快写 template <typename T> inline void write(T x) {if (x < 0) { putchar('-'); x = -x; }if (x > 9) write(x / 10);putchar(x % 10 + '0'); }struct node {int x, y, z, v, ans;node (int x, int y, int z){this->x = x;this->y = y;this->z = z;this->v = 1;this->ans = 0;}node (){} };int MAXN = 1e5+5; int MAXK = 2e5+5; vector<node> a(MAXN); vector<node> b(MAXN); vector<int> sz(MAXK, 0);int low_bit(int x){return x & -x; }void add(int x, int v){while(x < MAXK){sz[x] += v;x += low_bit(x);} }int querry(int x){int rst = 0;while(x > 0){rst += sz[x];x -= low_bit(x);}return rst; }int cmp(node a, node b){if(a.x == b.x){if(a.y == b.y){return a.z < b.z;}return a.y < b.y;}return a.x < b.x; }void cdq(int l, int r){if(l >= r) return;int mid = l + ((r-l) >> 1);cdq(l, mid);cdq(mid+1, r);//计算左部分对右部分的贡献int i = l;for(int j = mid+1; j <= r; j++){while(i <= mid && a[i].y <= a[j].y){add(a[i].z, a[i].v);i++;}a[j].ans += querry(a[j].z);}//树状数组回滚还原for(int k = l; k < i; k++){add(a[k].z, -a[k].v); }//按y排序 为下一次cdq做准备int pos = l, rr = mid+1, ll = l;while(rr <= r && ll <= mid){if(a[ll].y <= a[rr].y){b[pos++] = a[ll++];}else {b[pos++] = a[rr++];}}while(rr <= r){b[pos++] = a[rr++];}while(ll <= mid){b[pos++] = a[ll++];}for(int k = l; k <= r; k++){a[k] = b[k];} }signed main(){IOS;int n, k;n = read<int>(); k = read<int>();for(int i = 0; i < n; i++){int x, y, z;x = read<int>(); y = read<int>(); z = read<int>();a[i] = node(x, y, z);}sort(a.begin(), a.begin()+n, cmp);//去重计数int j = 0;for(int i = 1; i < n; i++){if(a[i].x == a[j].x && a[i].y == a[j].y && a[i].z == a[j].z){a[j].v++;}else {a[++j] = a[i];}}cdq(0, j);vector<int> ans(MAXN, 0);for(int i = 0; i <= j; i++){ans[a[i].ans + a[i].v - 1] += a[i].v;}for(int i = 0; i < n; i++){write(ans[i]);putchar('\n');} }P5094 MooFest G 加强版 - 洛谷
思路：
对题意进行转化， 存在n个点\((x, v)\)， 求\[\]
对于点对\((i, j)\)和\((j, i)\)而言二者相同， 因此我们可以先对\(v\)进行排序$$
不妨假设排序后\(v_i > v_j (i > j)\) ，此时的求和公式变成了\[ \sum_{i=1}^nv_i×\sum_{j=1}^{i-1}abs(x_i - x_j) \]我们发现此时一个点对答案所做的贡献只受影响于其左侧的点， 故我们可以进行CDQ分治 在每次递归中统计左部分$x$的前缀和，使用双指针，若左指针$x$小于右指针$x$则从前缀和中减去左指针的部分， 该部分的$x$之差为正， 当左指针的$x$不再小于右指针时， 左侧区间的剩余部分均大于右指针， 该部分的$x$之差为负数， 如此便可算出左侧区间对当前右指针的贡献
按照\(x\)大小对左右部分进行归并， 维持\(x\)的单调性int ll = l;for(int i = mid+1; i <= r; i++){while(a[ll].x < a[i].x && ll <= mid){ss += a[ll].x;sl -= a[ll].x;ll++;}ans += (a[i].y * (((ll-l) * a[i].x - ss) + (sl - (mid-ll+1) * a[i].x)));}
时间复杂度\(O(nlogn)\)
代码如下：#include <bits/stdc++.h> using namespace std; #define int long long #define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)int MAXN = 5e4+10, n, ans = 0;struct node {int x, y;node (int x, int y){this->x = x;this->y = y;}node (){} };vector<node> a(MAXN); vector<node> temp(MAXN);int cmp(node a, node b){return a.y < b.y; }void cdq(int l, int r){if(l >= r) return ;int mid = (l + r) >> 1;cdq(l, mid);cdq(mid+1, r);int sl = 0, ss = 0;for(int i = l; i <= mid; i++){sl += a[i].x;}int ll = l;for(int i = mid+1; i <= r; i++){while(a[ll].x < a[i].x && ll <= mid){ss += a[ll].x;sl -= a[ll].x;ll++;}ans += (a[i].y * (((ll-l) * a[i].x - ss) + (sl - (mid-ll+1) * a[i].x)));}int i = l, j = mid+1, cnt = l;while(i <= mid && j <= r){if(a[i].x <= a[j].x){temp[cnt++] = a[i++];}else {temp[cnt++] = a[j++];}}while(i <= mid){temp[cnt++] = a[i++];}while(j <= r){temp[cnt++] = a[j++];}for(int i = l; i <= r; i++){a[i] = temp[i];} }signed main(){IOS;cin >> n;for(int i = 0; i < n; i++){node t;cin >> t.y >> t.x;a[i] = t;}sort(a.begin(), a.begin()+n, cmp);cdq(0, n-1);cout << ans; }P7883 平面最近点对（加强加强版） - 洛谷
思路：
$$
min_{(i \neq j)}({\sqrt{(x_i-x_j)^2 + (y_i - y_j)^2}})
$$
当所有点依照\(x\)单调排列时我们可以将整个区间分成两部分，最小距离的点对无非三种情况
1. 全部位于左半部分
2. 全部位于右半部分
3. 一左一右
由此我们可以先分别求出左右部分的最短距离\(midis\)，即完成了第一和第二种情况的讨论那么对于第三种情况我们只需要从中点分别向左右部分延伸\(midis\)的距离作为中间部分，即得到了所有可能成为最小值的跨越两个部分的点对的情况，再计算最小值;故我们先对所有点按照\(x\)排序；
当我们从上一步递归得到左右区间的最小值后按照\(y\)的大小进行归并排序，再遍历整个区间， 将处在中间区间的点加入一个数组中，在该数组中再次计算最小距离；此处判断\(x\)合法的每个点对的\((y_i - y_j)\)是否合法， 由于此时\(y\)单调 若此\(y_j\)不合法则对于当前的\(y_i\)后续的所有\(y_j\)均不合法，通过剪枝大大提高了效率；
最后返回最小值即为区间\([l, r]\)中的最小点对距离
时间复杂度\(O(nlogn)\)
代码如下：#include <bits/stdc++.h> using namespace std; #define int long long #define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)int MAXN = 5e4+10, n, ans = 0;struct node {int x, y;node (int x, int y){this->x = x;this->y = y;}node (){} };vector<node> a(MAXN); vector<node> temp(MAXN);int cmp(node a, node b){return a.y < b.y; }void cdq(int l, int r){if(l >= r) return ;int mid = (l + r) >> 1;cdq(l, mid);cdq(mid+1, r);int sl = 0, ss = 0;for(int i = l; i <= mid; i++){sl += a[i].x;}int ll = l;for(int i = mid+1; i <= r; i++){while(a[ll].x < a[i].x && ll <= mid){ss += a[ll].x;sl -= a[ll].x;ll++;}ans += (a[i].y * (((ll-l) * a[i].x - ss) + (sl - (mid-ll+1) * a[i].x)));}int i = l, j = mid+1, cnt = l;while(i <= mid && j <= r){if(a[i].x <= a[j].x){temp[cnt++] = a[i++];}else {temp[cnt++] = a[j++];}}while(i <= mid){temp[cnt++] = a[i++];}while(j <= r){temp[cnt++] = a[j++];}for(int i = l; i <= r; i++){a[i] = temp[i];} }signed main(){IOS;cin >> n;for(int i = 0; i < n; i++){node t;cin >> t.y >> t.x;a[i] = t;}sort(a.begin(), a.begin()+n, cmp);cdq(0, n-1);cout << ans; }