emmmm我能怎么说呢
CDQ分治显然我没法写一篇完整的优秀的博客，因为我自己还不是很明白...
因为这玩意的思想实在是太短了：
fateice如是说道：
如果说对于一道题目的离线操作，假设有n个操作
把n个操作分成两半，可以想到的是，假如说提出上面那半的修改操作，下面那半提出询问操作
那么这些修改操作对下面的询问操作显然是都产生了相同的影响的。
然后对于每一半的操作都这样递归下去，然后就有了CDQ分治处理问题的基本方法
（图片来自fateice大爷的怕怕踢）
但是再往深处说我也不知道该怎么说，等研究的更深入了再把CDQ分治的完整博客写出来吧
如果哪位路过的好心人看见了，记得催更
丢一篇大佬的上古博客：https://www.cnblogs.com/mlystdcall/p/6219421.html（希望大佬不要diss我私自搬他的博客的链接）
下面是题目：
Description
有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性
Output
包含N行，分别表示评级为0...N-1的每级花的数量。
Sample Input
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
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
Sample Output
3
1
3
0
1
0
1
0
0
1
1
3
0
1
0
1
0
0
1
emmm读完题目后我们显然的可以想到这是三维偏序的CDQ分治的基本题
然后就是对一维排序，对第二维CDQ分治，同时用树状数组处理第三维
但实际上我是把这题当成学习板子的板子题写的，所以我代码基本是学习别人的...
这题比较坑的地方是，对于属性值完全相同的花来说，各自互相美于对面，
这就好像你和你的几个克隆体站在一起，你比你的克隆体们聪明，你的克隆体们比你的克隆体们聪明，你的克隆体们又比你聪明...
或者说是，你把一份代码复制成数份，然后你的代码比你的代码优秀，你的代码又比你的代码优秀..
处理方式简单讲就是先把所有属性值相同的花都记一个数量，然后当做一种花处理，最后处理评级时再给加上...
总之具体处理过程还是看代码吧...至少代码里有注释....
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
using namespace std;
const int maxn = ;
struct Query {
int s, c, m;
int num, sum;
bool operator < (const Query &A) const {
return c == A.c ? m < A.m : c < A.c;
}
bool operator != (const Query &A) const {
return s != A.s || c != A.c || m != A.m;
}
}a[maxn], q[maxn];
int n, k, cnt = , top = ;
int c[maxn << ];
int ans[maxn]; inline int read() {
int x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y = -;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} inline bool cmp(Query x, Query y) {//按第一维排序
if(x.s == y.s && x.c == y.c) return x.m < y.m;
else if(x.s == y.s) return x.c < y.c;
return x.s < y.s;
} inline int ask(int x) {
int res = ;
for(; x; x -= (x & -x)) res += c[x];
return res;
} inline void add(int x, int y) {
for(; x <= k; x += (x & -x)) c[x] += y;
} void solve(int l, int r) {
if(l == r) return;
int mid = l + r >> ;
solve(l, mid), solve(mid + , r);
sort(q + l, q + mid + );//排序，让我sb的卡了会，因为不知道sort的排序是左闭右开
sort(q + mid + , q + r + );
int x = l;
for(int i = mid + ; i <= r; ++i) {//用左边区间的答案导出右边区间的答案
while(x <= mid && q[x].c <= q[i].c) add(q[x].m, q[x].num), x++;//确定了前两维的顺序时，将q[x].m赋上该品种的花的数量，方便右边区间查询
q[i].sum += ask(q[i].m);//查询
}
for(int i = l; i < x; ++i) add(q[i].m, -q[i].num);//还原树状数组
} int main() {
n = read(), k = read();
for(int i = ; i <= n; ++i)
a[i].s = read(), a[i].c = read(), a[i].m = read();
sort(a + , a + n + , cmp);
for(int i = ; i <= n; ++i) {
cnt++;
if(a[i] != a[i + ]) {
q[++top] = a[i];
q[top].num = cnt;//对于某一品种花有多少个
cnt = ;
}
}
solve(, top);
for(int i = ; i <= top; ++i) ans[q[i].sum + q[i].num - ] += q[i].num;
//一朵花的评级=该朵花的美丽值超越的花的数量+属性相同的花的总量(包含自己)-1
//因为题目：定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
for(int i = ; i < n; ++i) printf("%d\n", ans[i]);
//评级可能有0的
return ;
}