【学习笔记】cdq 分治
NCC79601
2019-10-20 00:05:18
由于太懒，我只学会了 cdq 分治解决逆序对问题。
**例题** [P3810](https://www.luogu.org/problem/P3810)
# 原理
**cdq 分治：** 对于一个区间$[l,r]$进行操作时，先对$[l,mid]$和$[mid+1,r]$进行操作，然后统计$[l,mid]$对$[mid+1,r]$的影响，最终得到结果，这样的过程就是 cdq 分治。
# 偏序问题
考虑对于$\forall i$，如何计算$a_i\geq a_j,b_i\geq b_j,c_i\geq c_j$的$j$的个数。
可以渐进地思考这个问题：
### 逆序对
直接搞个权值树状数组作为一个桶，然后从右到左扫一遍；或者归并排序统计答案即可。当然也可以用与解决顺序对问题。
### 二维偏序
如果是二维，考虑对一维的每个数构造数对$(i,a_i)$，显然对于一个顺序对$(a_i,a_j)$有$i<j,a_i<a_j$，么按$a$排序以后，就转化为了一维顺序对问题。
这样就得出了一个很重要的结论：在偏序问题中，只要有一位有序，那么就可以**直接忽略**这一维。这也为降维提供了可能性。
回到三维偏序问题，假设$a$有序，那么就可以直接忽略$a$的影响了；再考虑对$b$进行类似于归并排序的处理，同时使用 cdq 分治，对$c$构造一个权值树状数组，每次只需要统计$c_j\leq c_i$的个数即可。
另外，还有两个坑点：
1. 树状数组在每次归并排序完成之后必须清空，否则会不停加下去；
2. $a,b,c$全部相等的情况需要特判处理。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 2e5 + 10;
struct _node {
int a, b, c, ans;
} node[MAXN];
int cnt[MAXN];
bool cmp1(const _node &lhs, const _node &rhs) {
if (lhs.a != rhs.a)
return lhs.a < rhs.a;
if (lhs.b != rhs.b)
return lhs.b < rhs.b;
return lhs.c < rhs.c;
}
bool cmp2(const _node &lhs, const _node &rhs) {
return lhs.b < rhs.b;
}
// cmp2 用于 cdq 分治
bool operator != (const _node &lhs, const _node &rhs) {
return (lhs.a != rhs.a) || (lhs.b != rhs.b) || (lhs.c != rhs.c);
}
int n, k, c[MAXK];
void add(int x, int val) {
for ( ; x <= k; x += x & (-x))
c[x] += val;
return ;
}
int query(int x) {
int res = 0;
for ( ; x; x -= x & (-x))
res += c[x];
return res;
}
void cdq(int l, int r) {
if (l == r)
return ;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
sort(node + l, node + mid + 1, cmp2);
sort(node + mid + 1, node + r + 1, cmp2);
int j = l;
for (int i = mid + 1; i <= r; i++) {
while (j <= mid && node[j].b <= node[i].b) {
add(node[j].c, 1);
j++;
}
node[i].ans += query(node[i].c);
}
while (--j >= l)
add(node[j].c, -1);
// attention!!
// 树状数组必须清空，否则凉凉
return ;
}
int main() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d %d %d",&node[i].a, &node[i].b, &node[i].c);
sort(node + 1, node + n + 1, cmp1);
for (int i = n, j = n; i >= 1; i--) {
while (node[i] != node[j])
j--;
node[i].ans += j - i;
printf(" > %d\n", node[i].ans);
}
// attention!!
// 特判 i < j 且 a, b, c 全部相等的情况
// 原因：cdq(l, r) 中的第一个 while 会把所有相等的都跳过
cdq(1, n);
for (int i = 1; i <= n; ++i)
cnt[node[i].ans]++;
for (int i = 0; i < n; i++)
printf("%d\n", cnt[i]);
return 0;
}
```