CDQ分治
前言
CDQ分治是一种分治
CDQ分治是一种特殊的分治思想
可以用于跟点对有关的问题
还有其他用处......（目前不会）
算法流程
一般来说，cdq 分治是通过如下结构进行分治
一共分为三步：
- 找到当前区间\([l,r]\)中点\(mid\)
- 递归处理左右区间\([l,mid]\),\([mid+1,r]\)
- 计算左区间对右区间的贡献
比如归并排序求逆序对
即二维偏序
将序列归并排序，在合并的时候计算左对右的贡献
这个过程就可以看作CDQ分治的思想
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,a[N],b[N],ans;
inline 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,now=l;//i,j表示左右指针，now表示b数组的指针
while(i<=mid&&j<=r){
if(a[i]<=a[j])b[now++]=a[i++];//不产生贡献
else{//产生贡献
b[now++]=a[j++];
ans+=mid-i+1;//计算贡献
}
}//可以看到跟归并排序一样 只是多了一个计算贡献
//这就是归并排序求逆序对的过程 可以看作是CDQ分治的思想
while(i<=mid)b[now++]=a[i++];
while(j<=r)b[now++]=a[j++];
for(int i=l;i<=r;i++)a[i]=b[i];
return;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
cdq(1,n);
printf("%lld",ans);
return 0;
}
再增加一维变成三维偏序
三维偏序是CDQ分治的经典问题
先用sort按x排序 消除第一维的影响
然后将序列拆分 按y归并排序
合并的时候利用树状数组计算贡献
详细来说计算贡献的过程是
维护左右区间指针\(i，j\)
合并时我们把所有\(y_i<y_j\)的点
全部插入到树状数组里。
此时只要查询树状数组里有多少个点的\(z\)值是小于\(z_j\)的即可
也就是\(z_j\)的前缀和
void Init(int x)//清空树状数组
{
for(;x<=s;x+=x&(-x))//s是值域
if(f[x]!=0) f[x]=0;
else break;
return;
}
void Insert(int x,const int &v)//单点插入
{
for(;x<=s;x+-=x&(-x)) f[x]+=v;
return ;
}
int Query(int x)//查询前缀和
{
int res=0;
for(;x;-=x &-x) res+=f[x];
return res;
}
void CdqSolve(const int &l,const int &r)
{
if(l==r) return;
int mid=l+r>>1,idx1=l,idx2=mid+1;
CdqSolve(l,mid);
CdqSolve(mid+1,r);
//先分治左右区间 合并时计算贡献
for(int i=l;i<=r;i++)
{
if(idx2>r || idx1<=mid && a[idx1]>a[idx2])
{
t[i]=a[idx1++];
Insert(t[i].z,t[i].cnt);//左区间的插入树状数组
}
else
{
t[i]=a[idx2++];
t[i].sum+=Query(t[i].z);//右区间的查询前缀和
}
}
for(int i=l;i<=r;i++)
{
a[i]=t[i];
Init(a[i].z);//清空树状数组
}
return;
}
再增加一维变成四维偏序。。。
好像要用CDQ分治套CDQ分治
也是坑 以后再填
附例题
大概题意是求当前点A曼哈顿距离最小的点B（K-D树板子）
先只考虑左下方的点
需要满足\(B_x<A_x,B_y<A_y\)
求\(B_x+B_y\)的最大值
每个点有三维 时间 x y
时间输入时就排好了
x用归并排序处理 y用树状数组
跟三维偏序一样
将整个平面翻转三次
每次都这样处理
所有点就都处理到了
引用来源
CDQ 分治 - OI Wiki (oi-wiki.org)
侵删
标签：偏序,树状,int,分治,mid,博客,CDQ From： https://www.cnblogs.com/zysssss/p/18083290