CDQ分治
CDQ 分治是一种思想而不是具体的算法，与 动态规划 类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：
- 解决和点对有关的问题。
- 1D 动态规划的优化与转移。
- 通过 CDQ 分治，将一些动态问题转化为静态问题。
解决和点对有关的问题
这类问题多数类似于「给定一个长度为 n 的序列，统计有一些特性的点对 
的数量/找到一对点 使得一些函数的值最大」。
CDQ 分治解决这类问题的算法流程如下：
- 找到这个序列的中点 ；
- 将所有点对 划分为 3 类：
- 的点对；
- 的点对；
- 的点对。
- 将 这个序列拆成两个序列 和 。此时第一类点对和第三类点对都在这两个序列之中；
- 递归地处理这两类点对；
- 设法处理第二类点对。
可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。
在实际应用时，我们通常使用一个函数 solve(l,r) 处理 的点对。上述算法流程中的递归部分便是通过 solve(l,mid) 与 solve(mid,r) 来实现的。剩下的第二类点对则需要额外设计算法解决。
例题
P3810 【模板】三维偏序（陌上花开） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template<typename T>
struct BIT {
#ifndef lowbit
#define lowbit(x) (x & (-x));
#endif
int n;
vector<T> t;
BIT () {}
BIT (int _n): n(_n) { t.resize(_n + 1); }
BIT (int _n, vector<T>& a): n(_n) {
t.resize(_n + 1);
for (int i = 1; i <= n; ++ i) {
t[i] += a[i];
int j = i + lowbit(i);
if (j <= n) t[j] += t[i];
}
}
//单点修改
void update(int i, T x) {
while (i <= n) {
t[i] += x;
i += lowbit(i);
}
}
//区间查询
T sum(int i) {
T ans = 0;
while (i > 0) {
ans += t[i];
i -= lowbit(i);
}
return ans;
}
T query(int i, int j) {
return sum(j) - sum(i - 1);
}
//区间修改则存入差分数组,[l, r] + k则update(x,k),update(y+1,-k)
//单点查询则直接求前缀和sum(x)
//求逆序对
/*
iota(d.begin(), d.end(), 0);
stable_sort(d.begin(), d.end(), [&](int x, int y) {
return a[x] < a[y];
});去重排序
BIT<i64> tree(n);
i64 ans = 0;
for (int i = 1; i <= n; i ++) {
tree.update(d[i], 1);
ans += i - tree.sum(d[i]);
}
*/
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<array<int, 3>> a(n);
for (auto &[x, y, z] : a)
cin >> x >> y >> z;
sort(a.begin(), a.end());
vector<array<int, 5>> A;
for (int i = 0; i < n; i ++) {
int j = i;
while (j + 1 < n && a[j + 1] == a[j]) {
j ++;
}
A.push_back({a[j][0], a[j][1], a[j][2], j - i + 1, 0});
i = j;
}
BIT<i64> bit(k);
auto cdq = [&](auto && self, int l, int r)->void{
if (l == r)
return ;
int mid = l + r >> 1;
self(self, l, mid);
self(self, mid + 1, r);
sort(A.begin() + l, A.begin() + mid + 1, [](auto x, auto y) {
if (x[1] == y[1]) return x[2] < y[2];
return x[1] < y[1];
});
sort(A.begin() + mid + 1, A.begin() + r + 1, [](auto x, auto y) {
if (x[1] == y[1]) return x[2] < y[2];
return x[1] < y[1];
});
int i = l, j = mid + 1;
while (j <= r) {
while (i <= mid && A[i][1] <= A[j][1]) {
bit.update(A[i][2], A[i][3]);
i ++;
}
A[j][4] += bit.sum(A[j][2]);
j ++;
}
for (int k = l; k < i; k ++)
bit.update(A[k][2], -A[k][3]);
};
cdq(cdq, 0, A.size() - 1);
vector<i64> f(n + 1);
for (auto &[a, b, c, cnt, d] : A) {
f[d + cnt - 1] += cnt;
}
for (int i = 0; i < n; i ++)
cout << f[i] << "\n";
return 0;
}
P5094 [USACO04OPEN] MooFest G 加强版 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<array<int, 2>> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
sort(a.begin(), a.end());
i64 ans = 0;
auto cdq = [&](auto && self, int l, int r)->void{
if (l == r)
return ;
int mid = l + r >> 1;
self(self, l, mid);
self(self, mid + 1, r);
sort(a.begin() + l, a.begin() + mid + 1, [](auto x, auto y) {
if (x[1] != y[1]) return x[1] < y[1];
return x[0] < y[0];
});
sort(a.begin() + mid + 1, a.begin() + r + 1, [](auto x, auto y) {
if (x[1] != y[1]) return x[1] < y[1];
return x[0] < y[0];
});
int sum1 = 0, sum2 = 0;
for (int i = l; i <= mid; i ++)
sum1 += a[i][1];
int i = l, j = mid + 1;
while (j <= r) {
while (i <= mid && a[i][1] < a[j][1]) {
sum1 -= a[i][1], sum2 += a[i][1];
i ++;
}
int cnt1 = i - l, cnt2 = mid - i + 1;
ans += 1ll * a[j][0] * (cnt1 * a[j][1] - sum2 + sum1 - cnt2 * a[j][1]);
j ++;
}
};
cdq(cdq, 0, n - 1);
cout << ans << '\n';
return 0;
}