对于题目 ：P4690 [Ynoi2016] 镜中的昆虫 我们零基础从各个小部分开始学习，并且 A 了 Ta.
Part 1 CDQ分治
一看到这个东西， 一定会觉得很吓人， 觉得是什么高大上的东西。其实不然， 且听我慢慢讲来。
先明白 ta 是用来干什么的， 解决三维偏序。 三维偏序是什么？
给定一个命题 \(j\) Ta 有三个属性 不妨设为
\(pos_{j_1} \enspace pos_{j_2} \enspace pos_{j_3}\)
问所有满足条件的命题 \(i\) 对 \(j\) 的贡献是什么。（\(i\) 也一样与 \(j\) 有三个对应的属性）
所谓满足条件， 就是这三个对应的属性同时满足指定的大小关系。
（关于模型的扩展后面会将 >w<）
有点抽象？ 上模板！
【模板】三维偏序（陌上花开）
题目背景
这是一道模板题，可以使用 bitset，CDQ 分治，KD-Tree 等方式解决。
题目描述
有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 \(j\) 的数量。
对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。
输入格式
第一行两个整数 $ n,k $，表示元素数量和最大属性值。
接下来 $ n $ 行，每行三个整数 $ a_i ,b_i,c_i $，分别表示三个属性值。
输出格式
$ n $ 行，第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。
样例 #1
样例输入 #1
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
样例输出 #1
3
1
3
0
1
0
1
0
0
1
提示
$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。
可以发现， 我们先前所说的三个元素， 在这里分别表示 \(a, b, c\)。
而所谓的大小关系在这一道题里面全都表现为 $ \ge$
那么考虑如何解决这个问题。
暴力的做法就是一个一个枚举去比较， 同时满足三个条件的就计入答案。
这是三个“愿望” 一次满足。
那么我们一个一个去满足 “愿望” 呢？
发现：三个约束条件在地位上是等价的， 也就是说先满足哪个都无所谓。这里我选择满足的顺序为 \(a, b, c\)
先考虑 \(a\)
直接 \(sort\) 按 \(a\) 的大小排序， 这样直接搞定第一个条件。
sort(tmp + 1, tmp + 1 + n, com);
现在我们排序好了！
再考虑后面两个条件， 并不是很好处理。于是CDQ分治就出现了！
首先我们假设要处理的序列长度为 \(n\)
定义 \(mid = (1 + n) / 2\)。
将该序列分为
\([1, mid], [mid + 1， n]\) 两个序列
先看看能不能快速计算前面一个序列对后面一个序列里的每个元素贡献。
显然，后面一个序列任意一个元素的 \(a\) 一定是大于等于 任意一个前面一个序列元素的 \(a\)。对于 \(a\) 的约束条件直接略去， 不看。
（\(a\)： 是不是不爱我了 qwq）
两部分都对 \(b\) 满足的条件去 \(sort\) 根据上面的依据， 两个队列这样排序完之后 对 “前序列对后序列元素”的贡献并无影响。
现在我们再一次排序好了！
这是候我们使用两个指针 \(L\) 和 \(R\) 起始位置
\(L = 1, R = mid + 1\)
对于\(R\) 每指到一个数字， 我们一直将 \(b_L \le b_R\) 的数放入备选区 并且使 \(L\) 指针向后移动(\(L ++\) )， 直到 \(L > mid \enspace || \enspace b_L < b_R\)。 这时候， 再从备选区中统计 \(R\) 的答案。统计完之后 \(R\)指针向后移动(\(R ++\))，直到 \(R == n\).
由于之前排过序的原因， \(L\) 一直往前， 备选区里面的元素始终都会满足当前 \(R\) 的 \(b\) 条件。 于是现在完成了两个“愿望”
现在考虑如何统计备选区的元素如何统计进答案。
假设当前备选区中有 \(k\) 个元素， 那么对于 \(R\) 的贡献为 \(\sum\limits_{i = 1}^k [c_i \le c_R]\), 直接使用权值树状数组去搞。（这应该很容易想到吧（雾））。
mid = (1 + n) >> 1;
int L = 1, R = mid + 1; //这是两个指针的起始位置
for(; R <= n; R ++){
while(L <= m && a[L].b <= a[R].b) Add(a[L].val, 1), L ++；//插入树状数组并且移动指针。
ans[a[R].id/*答案编号*/] += Query(a[R].c);
}
现在我们统计完了答案， 发现成功的求出了前一个区间对后一个区间里元素的贡献。这当然是不够的， 发现对于任意一个区间都可以进行类似的操作， 于是我们分而治之， 直接递归处理。
先在不是对于区间\([1, n]\), 而是更一般的 \([l, r]\)
只要修改一下变量即可
\(mid = (l + r) >> 1\)
\(L = l, R = mid + 1\)
递归的底层就是 \(l == r\)
别忘了递归下去做的时候把树状数组清空！
正确性先感性理解一发，举例序列原长为 \(9\)，看看哪些元素对 \(7\) 有贡献。由于对 \(a\) 的限制， 那么 \(8 \sim 9\)是不会对 \(7\) 有贡献的。
开始分治（qwq）
第一次 对 \([1, 9]: [1, 5]\) \([6, 9]\) 那么计算了 \([1, 5]\) 对 \(7\) 的贡献
之后\([1, 5]\) 对 \(7\) 没有影响了， 直接跳过不去看他
第二次 对 \([6, 9]: [6, 7]\) \([8, 9]\)
对 \(7\) 无影响， 之后对于 \(7\) , \([8, 9]\)也无用了
第三次 对 \([6, 7] : [6, 6] [7, 7]\) 计算了 \([6, 6]\) 对 \(7\) 的贡献。
递归结束。
综上， 我一共统计了 \([1, 6]\) 对 \(7\) 的贡献！正好是我们暴力所作的 >w<
上代码 ： （可能变量申明会有所不同）
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int tr[N];
int l_ans[N];
struct T{
int a, b, c, ans, cnt;
}cd[N], tmp[N];
int bs(int x){
return x & (-x);
}
void clear(){
memset(tr, 0, sizeof(tr));
}
int n, k;
bool com(T x, T y){
if(x.a == y.a && x.b == y.b)
return x.c < y.c;
if(x.a == y.a)
return x.b < y.b;
return x.a < y.a;
}
void Add(int x, int val){
while(x <= k){
tr[x] += val;
x += bs(x);
}
return ;
}
int query(int x){
int ans = 0;
while(x > 0){
ans += tr[x];
x -= bs(x);
}
return ans;
}
bool com1(T x, T y){
if(x.b == y.b)
return x.c < y.c;
return x.b < y.b;
}
void cdq(int l, int r){
if(l == r) return;//到头就直接run
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);//先递归处理两边qqq
sort(cd + l, cd + mid + 1, com1);
sort(cd + mid + 1, cd + r + 1, com1);
int L = l, R = mid + 1;
for(; R <= r; R ++){
while(L <= mid && cd[L].b <= cd[R].b)
Add(cd[L].c, cd[L].cnt), L ++;
cd[R].ans += query(cd[R].c);
}
for(int i = l; i < L; i ++)
Add(cd[i].c, -cd[i].cnt);
return;
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++){
scanf("%d%d%d", &tmp[i].a, &tmp[i].b, &tmp[i].c);
// tmp[i].id = i;
}
// tmp[n + 1] = {-114514, -1919810, -190307, 0};
sort(tmp + 1, tmp + 1 + n, com);
int tot = 0;
int m = 0;
for(int i = 1; i <= n; i ++){
tot ++;
if(tmp[i].a != tmp[i + 1].a || tmp[i].b != tmp[i + 1].b || tmp[i].c != tmp[i + 1].c){//这边是合并了同类元素
cd[++ m] = tmp[i];
cd[m].cnt = tot;
tot = 0;
}
}
cdq(1, m);
for(int i = 1; i <= m; i ++)
l_ans[cd[i].ans + cd[i].cnt - 1] += cd[i].cnt;
for(int i = 0; i < n; i ++)
printf("%d\n", l_ans[i]);
return 0;
}