CDQ分治
定义
CDQ分治主要解决偏序问题（问题包含修改和查询操作），通过对一维进行排序，在对其他维度进行分治。
【注意】
使用CDQ分治解决问题，问题要满足以下条件
- 修改操作对查询的贡献是独立的
- 修改操作互不影响
- 可以使用离线算法
前置知识
偏序
形式定义
设R是集合A上的一个二元关系，若R满足：
Ⅰ 自反性：
- 对任意x∈A，有xRx；
Ⅱ 反对称性（即反对称关系）： - 对任意x,y∈A，若xRy，且yRx，则x=y；
Ⅲ 传递性： - 对任意x, y,z∈A，若xRy，且yRz，则xRz。
则称R为A上的偏序关系，通常记作 ≼ 。注意这里的 ≼ 不必是指一般意义上的“小于或等于”。若然有x≼y，我们也说x排在y前面（x precedes y）。
即指的是 “只有一部分元素之间能比出大小”
一维偏序
定义
对于一维偏序，通常我们关注的是如何在一维序列中比较元素的大小关系。
例如
给定一个数列 \(a_1, a_2, \ldots, a_n\)我们可以定义一个偏序关系 \(a_i \leq a_j\)。即在长度为n的序列中求出每个元素在序列中比其小于或等于的元素数目。
处理方式
将原序列升序排序。
二维偏序
定义
对于平面上的两个点 A(x₁, y₁) 和 B(x₂, y₂)，如果 x₁ ≤ x₂ 并且 y₁ ≤ y₂，我们就称点 A “偏序小于” 点 B，记作 A ≤ B。
例如
有n个元素，第i个元素有\(a_i\) \(b_i\)两个属性，求出对于每个下标i,满足 \(j\ne i\) , \(a_j\le a_i\) 且 \(b_j\le b_i\) 的j的数目。
将问题具体化：
即对于平面上的每个点 i，求出有多少个点 j 满足 j ≤ i
处理方式
1.归并排序（时间复杂度O(nlogn)）
- 先按照\(a_i\)进行排序，然后对\(b_i\)进行归并排序。
- 归并排序时，序列被划分为[l,mid],[mid+1,r]两个序列。
- 虽然按照\(b_i\)进行归并排序会导致\(a_i\)的顺序混乱，但两个序列仍满足左边序列的\(a_i\)不大于右边序列的\(a_i\)。
- 用双指针合并两个序列时，若要存放右边序列的元素，可以根据左边指针和左边界的相对位置计算其贡献
2.树状数组（时间复杂度O(nlogn)）
- 先按照\(a_i\)进行排序，然后开树状数组维护当前遍历位置之前值小于等于\(b_i\)的元素数目
*遍历按照第一维排序后的序列，\(ans[i]=find(b[i])\)
三维偏序
定义
是指在三维空间中，元素之间的偏序关系。具体来说，给定一个序列，每个元素有三个属性 \(a_i, b_i, c_i\)，我们可以定义一个偏序关系，满足 \(a_j \leq a_i\) , \(b_j \leq b_i\)和 \(c_j \leq c_i\)的点对 \((i, j)\) 被认为是偏序的。
例子
洛谷 P3810 【模板】三维偏序（陌上花开）
有n个元素，第i个元素有\(a_i\) \(b_i\) \(c_i\)三个属性，设\(f(i)\)表示满足 \(j\ne i\) 且 \(a_j\le a_i\) \(b_j\le b_i\) \(c_j\le c_i\)的数量。
对于\(d∈[0,n)\),求\(f(i)=d\)的\(i\)的个数。
处理方式$ \Downarrow$
CDQ分治
基本思想
- 问题包含修改和查询操作，把问题排成一个序列，用一个区间 [L,R] 表示。
- 分：递归处理左边区间 [L,MID] 和右边区间 [MID+1,R] 的问题。
- 治：合并两个子问题，考虑 [L,MID] 内的修改对 [MID+1,R] 内的查询产生的影响；即用左边的子问题帮助解决右边的子问题。
例题
洛谷 P3810 【模板】三维偏序（陌上花开）
思路
将第一维排序，第二维CDQ分治,第三维套用权值树状数组
代码
#include<bits/stdc++.h>
using namespace std;
struct jade
{int a,b,c,ans,cnt;
}s1[200010],s2[200010];
int n,m,k,maxx,top,f[200010];
int tree[200010];//树状数组
bool cmp1(jade x,jade y)//第一维排序
{if(x.a==y.a){if(x.b==y.b){return x.c<y.c;}else{return x.b<y.b; } }else{return x.a<y.a;}
}
bool cmp2(jade x,jade y)//第二维排序
{if(x.b==y.b){return x.c<y.c;}else{return x.b<y.b; }
}
//树状数组
int lowbit(int x)
{return x&(-x);
}
void add(int x,int y)
{for(int i=x;i<=maxx;i+=lowbit(i)){tree[i]+=y; }
}
int find(int x)
{int res=0;for(int i=x;i>0;i-=lowbit(i)){res+=tree[i]; } 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(s2+l,s2+mid+1,cmp2);sort(s2+mid+1,s2+r+1,cmp2);//第二维为关键字排序 int j=l;for(int i=mid+1;i<=r;i++){while(s2[i].b>=s2[j].b&&j<=mid){add(s2[j].c,s2[j].cnt);j++;}s2[i].ans+=find(s2[i].c);}for(int i=l;i<j;i++){add(s2[i].c,-s2[i].cnt);//清空树状数组 }
}
int main()
{cin>>n>>k;maxx=k;//树状数组区间 for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;s1[i].a=a;s1[i].b=b;s1[i].c=c;}sort(s1+1,s1+1+n,cmp1);//第一维为关键字排序 for(int i=1;i<=n;i++){top++;if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c){m++;s2[m].a=s1[i].a;s2[m].b=s1[i].b;s2[m].c=s1[i].c;s2[m].cnt=top;top=0;}}//第一维有序，合并节点 cdq(1,m);//CDQ分治 for(int i=1;i<=m;i++){f[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;//这些s2[i].cnt个元素他们的f值皆为s2[i].ans+s2[i].cnt-1 } for(int i=0;i<n;i++){cout<<f[i]<<endl;}
}
洛谷 P4390 [BalkanOI 2007] Mokia 摩基亚
思路
对于每一个询问的矩阵\(（x1,y1）\)\(（x2,y2）\)，考虑利用容斥小技巧把它拆成四个询问
- \(（0,0）\)\(（x2,y2）\)、\(（0,0）\)\(（x1-1,y1-1）\)
- 以及\(（0,0）\)\(（x1-1,y2）\)、\(（0,0）\)\(（x2,y1-1）\)
前者对答案做出正贡献而后者做出负贡献。
只有横坐标，纵坐标，以及出现时间三者都小于当前询问的才能对当前询问做出贡献。
考虑到是三位偏序问题，使用CDQ分治解决。
x1-1和y1-1可能为零，这会导致树状数组死循环。
所以我们需要把所有坐标都+1，还有w也别忘了+1，且这里不用去重。
考虑我们的元素特点。对于修改操作，我们不需要记录答案，对于询问操作，它没有做出贡献。所以我们只需在第一次排序时保证所有询问操作在三维都相等的修改操作之后就可以保证所有修改的贡献都被统计。这可以通过修改cmp函数实现。
代码
#include<bits/stdc++.h>
using namespace std;
struct jade
{int x,y,t;int pos,opt,val;//询问位置，操作种类，贡献
}a[200010],b[200010];
int ans[200010],tr[200010];
int x,y,xx,yy,times,cnt,qcnt,num,w,opts;
bool cmp(jade x,jade y)
{if(x.x!=y.x){return x.x<y.x;} if(x.y!=y.y){return x.y<y.y;}if(x.t!=y.t){return x.t<y.t;}return x.val>y.val;//和模板的不同之处 }
int lowbit(int x)
{return x&(-x);
}
void add(int x,int y)
{for(int i=x;i<=cnt;i+=lowbit(i)){tr[i]+=y;}
}
int find(int x)
{int res=0;for(int i=x;i;i-=lowbit(i)){res+=tr[i];}return res;
}
void cdq(int l,int r)//cdq分治模板
{if(l==r){return ;}int mid=(l+r)>>1;cdq(l,mid);//递归处理cdq(mid+1,r);int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i].y<=a[j].y)//左边小，插入{if(!a[i].opt){add(a[i].t,a[i].val);}b[k]=a[i];k++;i++;}else//右边小，算贡献{if(a[j].opt){int sum=find(a[j].t);ans[a[j].pos]+=sum*a[j].opt;}b[k]=a[j];k++;j++;}}while(j<=r)//注意此时可能没有完成统计{if(a[j].opt){int sum=find(a[j].t);ans[a[j].pos]+=sum*a[j].opt;}b[k]=a[j];k++;j++;}for(int p=l;p<i;p++)//还原树状数组{if(!a[p].opt){add(a[p].t,-a[p].val);}}while(i<=mid){b[k]=a[i];k++;i++;}for(int p=l;p<=r;p++){a[p]=b[p];}
}
int main()
{cin>>w>>w;w++;while(1){cin>>opts;if(opts==1){cin>>x>>y>>num;x++;y++;times++;cnt++;a[cnt]=jade{x,y,times,0,0,num};}else if(opts==2){cin>>x>>y>>xx>>yy;xx++;yy++;qcnt++;cnt++;a[cnt]=jade{xx,yy,times,qcnt,1,0};//容斥 cnt++;a[cnt]=jade{x,yy,times,qcnt,-1,0};cnt++;a[cnt]=jade{xx,y,times,qcnt,-1,0};cnt++;a[cnt]=jade{x,y,times,qcnt,1,0};}else{break;}}sort(a+1,a+1+cnt,cmp);cdq(1,cnt);for(int i=1;i<=qcnt;i++){cout<<ans[i]<<endl;}return 0;
}