\(\texttt{0x00}\)：前置芝士
- 归并排序；
- 树状数组；
- 重载运算符（这个大概都会吧）。
\(\texttt{0x01}\)：介绍
cdq 分治是一种离线分治算法，可用来处理以下几种问题：
- 解决和点对有关的问题。
- 1D 动态规划的优化与转移。
- 通过 CDQ 分治，将一些动态问题转化为静态问题。
它们的本质都是通过一系列转化将原问题转化为三维偏序问题。
\(\texttt{0x02}\)：梦开始的地方
我们都知道，求二维偏序（比如逆序对）可以用归并排序或树状数组，他们的本质都是先确定一维的顺序，再计算另一维贡献。
那拓展到三维偏序也是如此，既然归并和树状数组都能确定一维的顺序，那把他们两个合起来不就能做三维偏序了吗？
确实是这样的。
先回顾一下归并排序求逆序对。
void merge_sort(int l, int r) {
if(l == r) return ;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1;
for(int k = l; k <= r; k++)
if(j > r || i <= mid && a[i] <= a[j]) tmp[k] = a[i++];
else tmp[k] = a[j++], res += mid - i + 1;
for(int k = l; k <= r; k++) a[k] = tmp[k];
}
流程是这样的：将当前处理的序列一分为二，对于 \(i,j\) 在同一边的情况，递归求解即可，我们只需要考虑在两边的情况。
不妨设 \(i\) 在左，\(j\) 在右，由于左右区间已经递归按数值排好序了，下标一开始就是有序的，所以 \(i\) 的下标一定小于 \(j\) 的下标，又因为左右两边的数值是单调递增的，所以可以用双指针扫描一遍求出答案，具体的，当 \(a[i] > a[j]\) 时，说明 \(a[i]\) 是第一个大于 \(a[j]\) 的数且后面的数都大于 \(a[i]\)，所以 \(a[j]\) 和 \(a[i\sim mid]\) 都构成逆序对，可以直接统计答案。
时间复杂度 \(O(n\log n)\)。
注意两个容易理解错的地方：
-
虽然说按照数值排序会打乱下标的顺序，但是排序是在区间内部进行的，也就是说，左右两部分是完全封闭地完成了排序，所以左边区间的下标一定小于右边区间内的下标；
-
由于分治是从下往上递归的，所以同区间内的两个数的贡献已经被算过，只用考虑跨区间的贡献。
现在在这个基础上加上一维，就再套个树状数组控制第三维就行了，具体说来，排序保证了第一维，归并保证了第二维，树状数组保证了第三维。
这道题还有一个魔鬼细节，就是这三维都可以取等号，也就是说假如 \(a,b\) 完全相同，\(a\) 在 \(b\) 左边，那么 \(f(a) = f(b) = 1\) 才对，但是 cdq 分治只会算左边给右边的贡献，所以实际算出来为 \(f(a) = 0,f(b) = 1\)。
先去重，思考一下不难发现假如有 \(k\) 个数都相同，那么树状数组中的所有修改都要从 \(1\) 变成 \(k\)，同时在最后还要加上内部的贡献 \(k - 1\)。
时间复杂度 \(O(n\log ^2n)\)。
\(\texttt{Code}\)：
#include <iostream>
#include <algorithm>
#define lowbit(x) x & -x
using namespace std;
const int N = 100010, M = 200010;
int n, vmax;
struct node{
int a, b, c, s, res; //s是数量，res 是去重后每个元素满足条件的个数
bool operator< (const node &o) const { //三关键字排序
if(a != o.a) return a < o.a;
if(b != o.b) return b < o.b;
return c < o.c;
}
bool operator== (const node &o) const {
return a == o.a && b == o.b && c == o.c;
}
}e[N], tmp[N];
int ans[N];
int tr[M];
void add(int x, int y) {
for(; x < M; x += lowbit(x)) tr[x] += y;
}
int ask(int x) {
int res = 0;
for(; x; x -= lowbit(x)) res += tr[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); //递归左右两边
int i = l, j = mid + 1;
for(int k = l; k <= r; k++) {
if(j > r || i <= mid && e[i].b <= e[j].b) add(e[i].c, e[i].s), tmp[k] = e[i++]; //套一个树状数组
else e[j].res += ask(e[j].c), tmp[k] = e[j++];
}
for(int k = l; k <= mid; k++) add(e[k].c, -e[k].s); //做完一次后必须要清空树状数组
for(int k = l; k <= r; k++) e[k] = tmp[k]; //归并排序
}
int main() {
scanf("%d%d", &n, &vmax);
int a, b, c;
for(int i = 0; i < n; i++) {
scanf("%d%d%d", &a, &b, &c);
e[i] = {a, b, c, 1};
}
sort(e, e + n);
int tt = 1;
for(int i = 1; i < n; i++) { //去重
if(e[i] == e[tt - 1]) e[tt - 1].s++;
else e[tt++] = e[i];
}
cdq(0, tt - 1);
for(int i = 0; i < tt; i++)
ans[e[i].res + e[i].s - 1] += e[i].s; //注意加上内部贡献
for(int i = 0; i < n; i++) printf("%d\n", ans[i]);
return 0;
}