我只是个萌新，写一篇学习笔记，希望可以帮助未来的自己和他人。如果有大佬看到了错误，您可以在评论区或者私信中指出，并且我非常欢迎您的纠错。
本博客还是从二维偏序开始铺垫，对cdq分治进行讲解（实际上是给自己讲，因为没人看）。
前置知识：归并排序
cdq分治的学习需要保证对归并排序的理解，虽然它是一个基础算法。
二维偏序问题
给定 \(n\) 个元素，第 \(i\) 个元素有两个属性 \(a_i\) 和 \(b_i\) ，设 \(f(i)\) 为满足 \(a_j \leq a_i,b_j \leq b_i,j \neq i\) 的 \(j\) 的个数，对于每一个 \(0 \leq d \leq n - 1\) ，求满足 \(f(i) = d\) 的 \(i\) 的个数。
我们可以发现，对于一个元素 \(i\) ，只有满足 \(a_j \leq a_i\) 的元素才有可能对 \(f(i)\) 产生贡献。
不就是要单个属性小于等于吗，太简单了！我们只需要对属性 \(a\) 单独排序即可！
那么属性 \(b\) 呢？注意到对 \(f(i)\) 有贡献的元素要满足 \(b_j \leq b_i\) ，那么在排序后，我们需要获取在某个元素前面的满足 \(b_j \leq b_i\) 的个数，这一部分显然使用值域 BIT ，按顺序跑元素，然后一个一个加入，然后求前缀和即可。
有一个问题，如果两个元素的 \(a\) 相同，然而 \(b\) 小一点的排到了后面，会发生什么？
这一个的贡献算不到了。
所以，在 \(a\) 相同的元素内，我们应该对 \(b\) 排序。
所以 cmp 函数长这个样子：
bool cmp(node x,node y){
if(x.a != y.a)return x.a < y.a;
return x.b < y.b;
}
到目前为止，我相信能来学 cdq 分治的大佬肯定能理解二维偏序，那么就进入我们的正题了：
三维偏序问题（cdq分治模板）
在二维偏序中，我们在满足 \(a\) 有序的情况下，对 \(b\) 使用值域 BIT 得到了答案。
现在三维偏序多了一个属性，我们无法在一次排序内对两个属性进行排序，怎么办呢...
对新进来的属性进行归并排序。
假设我们一开始排序 \(a\) ,对 \(b\) 跑归并，对 \(c\) 用值域 BIT。
在归并排序的过程中，分析左边区间对右边区间的贡献。
为什么可以这样算？
由于归并排序是把原来的数组拆成一半一半的小区间，在拆的过程中我们未曾改变顺序，所以第一次开始算的时候，\(a\) 是有序的！
然后，我们合并区间上去，由于我们之前只是在小区间内合并，对于右边的大区间，我们的 \(a\) 仍然是有序的！
所以，我们可以直接分析左边区间对右边区间的贡献了（右边区间内部自己的贡献，和左边区间内部自己的贡献并不在考虑范围内，这部分会在之前更小的区间的归并排序过程中计算出来）。
这部分长这个样子。
void solve(int l,int r){
int mid = (l + r) / 2;
if(l == r)return ;
solve(l,mid);
solve(mid + 1,r);
int posl = l,posr = mid + 1;
int tot = l;
while(posl <= mid && posr <= r){
if(e[posl].b <= e[posr].b){
t.update(e[posl].c,e[posl].cnt);
tmp[tot ++] = e[posl ++];
}
else {
e[posr].val += t.query(e[posr].c);
tmp[tot ++] = e[posr ++];
}
}
while(posl <= mid){
t.update(e[posl].c,e[posl].cnt);
tmp[tot ++] = e[posl ++];
}
while(posr <= r){
e[posr].val += t.query(e[posr].c);
tmp[tot ++] = e[posr ++];
}
for(int i = l;i <= mid;i ++)t.update(e[i].c,-e[i].cnt);
for(int i = l;i <= r;i ++)e[i] = tmp[i];
}
解释一下，这个题有重点，这个 cnt 就是与这个点相同的点的个数。
f 就是这个元素的函数值。
在“并”的过程中，我们保证了 \(b\) 一定是排序好的，既然如此，我们就可以对 \(c\) 用值域 BIT 了。对于左边的区间，进行一个值域树状数组的加，对于右边的区间，直接在值域 BIT 中属性 \(c\) 小于它的个数，值域 BIT 里面只有左区间的元素，所以这就是左区间对右区间的贡献。
这个题就结束了。
由于 cdq分治 只能一次性处理完，所以跑 cdq分治 需要如下条件：
-
修改操作对询问的贡献独立，修改操作相互不影响
-
题目可以离线处理
cdq分治（在这个题中）实际上帮助我们做到的是通过对时间复杂度增加一个log来降维。
那么，跟上面讲解一样的，在cdq分治中，对于划分出来的两个区间，前一个子问题需要用来解决后一个子问题。
想必到这里，不会有人不懂了吧（
不懂欢迎问我。
贴上完整代码。
#include<bits/stdc++.h>
#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define frein freopen("in.in","r",stdin)
#define freout freopen("out.out","w",stdout)
#define debug(x) cout << (#x) << " = " << x << endl;
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
int MAXM;
int lowbit(int x){return x & -x;}
struct BIT{
int e[200010];
void update(int i,int x){for(;i <= MAXM;i += lowbit(i))e[i] += x;}
int query(int i){
int s = 0;
for(;i;i -= lowbit(i))s += e[i];
return s;
}
}t;
struct node{
int a;
int b;
int c;
int cnt;
int val;
}e[100010],tmp[100010];
int n;
int ans[100010];
int cnt = 1;
bool cmp(node x,node y){
if(x.a != y.a)return x.a < y.a;
if(x.b != y.b)return x.b < y.b;
return x.c < y.c;
}
void solve(int l,int r){
int mid = (l + r) / 2;
if(l == r)return ;
solve(l,mid);
solve(mid + 1,r);
int posl = l,posr = mid + 1;
int tot = l;
while(posl <= mid && posr <= r){
if(e[posl].b <= e[posr].b){
t.update(e[posl].c,e[posl].cnt);
tmp[tot ++] = e[posl ++];
}
else {
e[posr].val += t.query(e[posr].c);
tmp[tot ++] = e[posr ++];
}
}
while(posl <= mid){
t.update(e[posl].c,e[posl].cnt);
tmp[tot ++] = e[posl ++];
}
while(posr <= r){
e[posr].val += t.query(e[posr].c);
tmp[tot ++] = e[posr ++];
}
for(int i = l;i <= mid;i ++)t.update(e[i].c,-e[i].cnt);
for(int i = l;i <= r;i ++)e[i] = tmp[i];
}
signed main(){
cin>>n>>MAXM;
for(int i = 1;i <= n;i ++){
e[i].a = read(),e[i].b = read(),e[i].c = read();
e[i].cnt = 1;
}
sort(e + 1,e + n + 1,cmp);
for(int i = 2;i <= n;i ++){
if(e[i].a == e[cnt].a && e[i].b == e[cnt].b && e[i].c == e[cnt].c)e[cnt].cnt ++;
else e[++ cnt] = e[i];
}
solve(1,cnt);
for(int i = 1;i <= cnt;i ++)ans[e[i].val + e[i].cnt - 1] += e[i].cnt;
for(int i = 0;i <= n - 1;i ++)printf("%lld\n",ans[i]);
return 0;
}
这个博客还没完，还会有一些简单例题。
关于整体二分：
请叫我填坑。
2022.2.23 13:24