CDQ分治

前言

CDQ分治是一种分治

CDQ分治是一种特殊的分治思想

可以用于跟点对有关的问题

还有其他用处......（目前不会）

---

算法流程

一般来说，cdq 分治是通过如下结构进行分治

一共分为三步：

1. 找到当前区间$[l,r]$中点$mid$
2. 递归处理左右区间$[l,mid]$,$[mid+1,r]$
3. 计算左区间对右区间的贡献

---

比如归并排序求逆序对

即二维偏序

将序列归并排序，在合并的时候计算左对右的贡献

这个过程就可以看作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分治

也是坑 以后再填

---

附例题

P3810 【模板】三维偏序（陌上花开）

P4169 [Violet] 天使玩偶/SJY摆棋子

大概题意是求当前点A曼哈顿距离最小的点B（K-D树板子）

先只考虑左下方的点

需要满足$B_x<A_x,B_y<A_y$

求$B_x+B_y$的最大值

每个点有三维 时间 x y

时间输入时就排好了

x用归并排序处理 y用树状数组

跟三维偏序一样

将整个平面翻转三次

每次都这样处理

所有点就都处理到了

---

引用来源

【学习笔记】cdq分治 - trsins

CDQ 分治 - OI Wiki (oi-wiki.org)

侵删