首页 > 其他分享 >CDQ 分治 && 整体二分

CDQ 分治 && 整体二分

时间：2025-01-20 20:44:10浏览次数：1  
标签：二分 mathit int t2 mid t1 ++ CDQ &&

CDQ 分治

主要用于解决偏序问题。在偏序问题中，以三维偏序居多。它是一种离线算法。

其实严格来说，它是一种思想而不是算法。它依赖于归并排序。

CDQ 分治也可以用于 1D/1D 动态规划的转移，不过目前暂不涉及。

偏序问题

什么是偏序？先从一维偏序说起。

一维偏序

给定 \(n\) 个点，每个点有一个属性 \(a_i\)，求满足 \(a_j<a_i\) 的点对的数量。

排个序就完了。

二维偏序

给定 \(n\) 个点，每个点有两个属性 \(a_i,b_i\)，求满足 \(a_j<a_i\land b_j<b_i\) 的点对的数量。

把第一维排序，第二维用归并排序或树状数组解决。说到归并排序，其实 CDQ 分治就是利用归并排序的思想做的，后面会提到。

其实逆序对问题就是二维偏序，只不过第一维是位置，已经排好序罢了。

三维偏序

这才是 CDQ 分治的重点。照例第一维排序解决，第二维归并排序，第三维树状数组。

在拿到一个区间 \([l,r]\) 时，我们默认 \([l,\mathit{mid}]\) 和 \([\mathit{mid}+1,r]\) 已经排好序，现在需要合并两个区间，我们从 \(l\) 扫到 \(r\)，在保证 \(b_j\le b_i\) 的基础上，往树状数组里添加 \(c_j\)；一旦 \(b_j>b_i\)，我们就在树状数组里查询。

CDQ 分治在关于如何排序 \([l,\mathit{mid}]\) 和 \([\mathit{mid}+1,r]\) 这个问题上有两种写法。一种是直接 \(\tt sort\) 排序，这样常数会大一点；另一种是在扫描 \(l\to r\) 的过程中归并排序，常数会小一点。时间复杂度是 \(O(n\log^2n)\) 的。

两种写法都给出来。

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(j<=mid&&s2[i].b>=s2[j].b){
			B.add(s2[j].c,s2[j].cnt);
			++j;
		}
		s2[i].ans+=B.sum(s2[i].c);
	}
	for(int i=l;i<j;++i) B.add(s2[i].c,-s2[i].cnt);
}

void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	int t1=l,t2=mid+1;
	for(int i=l;i<=r;++i)
		if((t1<=mid&&a[t1].b<=a[t2].b)||t2>r){
			B.add(a[t1].c,a[t1].cnt);
			b[i]=a[t1++];
		}else{
			a[t2].ans+=B.sum(a[t2].c);
			b[i]=a[t2++];
		}
	for(int i=l;i<t1;++i) B.add(a[i].c,-a[i].cnt);
	for(int i=l;i<=r;++i) a[i]=b[i];
}

例题

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

板子。这题需要注意的是可能有多个点的 \(a_i,b_i,c_i\) 是相同的，所以读入之后需要先预处理一下个数，之后统计答案的时候也要额外计算一下。

void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	int t1=l,t2=mid+1;
	for(int i=l;i<=r;++i)
		if((t1<=mid&&a[t1].b<=a[t2].b)||t2>r){
			B.add(a[t1].c,a[t1].cnt);
			b[i]=a[t1++];
		}else{
			a[t2].ans+=B.sum(a[t2].c);
			b[i]=a[t2++];
		}
	for(int i=l;i<t1;++i) B.add(a[i].c,-a[i].cnt);
	for(int i=l;i<=r;++i) a[i]=b[i];
}

int main(){
	n=read(),K=read();
	for(int i=1;i<=n;++i) s1[i]={read(),read(),read(),0,0};
	sort(s1+1,s1+n+1);
	for(int i=1,top=0;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){
			a[++m]={s1[i].a,s1[i].b,s1[i].c,top,0};
			top=0;
		}
	}
	cdq(1,m);
	for(int i=1;i<=m;++i)
		ans[a[i].ans+a[i].cnt-1]+=a[i].cnt;
	for(int i=0;i<n;++i) write(ans[i]);
	return fw,0;
}

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

好的，带修了。其实让离线算法带修并不难，仿照当初处理莫队的手法，给它加上一维时间维即可。

接着考虑怎么处理这个坐标问题。思路是巧妙的：首先有两点之间曼哈顿距离公式：

\[\text{dis}(A,B)=|x_A-x_B|+|y_A-y_B| \]

绝对值很麻烦，所以我们暂时只考虑在原点左下方的点，就可以把绝对值去掉了。去掉绝对值之后，\(\text{dis}(A,B)\) 的最小值就是在当 \(x_B+y_B\) 最大时取到。于是问题转化为：求满足 \(\mathit{tm}_A>\mathit{tm}_B\land x_A\ge x_B\land y_A\ge y_B\) 时 \(x_B+y_B\) 的最大值。树状数组可以做。

剩下的点，可以旋转坐标使其和上面的问题一样。坑点不少：

  • 每次 CDQ 完时间维 \(\mathit{tm}\) 会被打乱，与其重新 \(O(n\log n)\) 排序不如直接 \(O(n)\) 复制过去。
  • 如果某个点在坐标轴上，即 \(x,y\) 坐标有 \(0\)，此时需要给全局加一，不然树状数组就失败~了。
  • 如果某一次翻转没有点在它的左下，树状数组会返回 \(0\)，如果不做处理的话程序就会以为存在一个 \(x+y\) 为 \(0\) 的点，但实际上没有，也不可能有（已经没有 \(x\) 或 \(y\) 坐标为 \(0\) 的点）。所以如果树状数组返回的结果是 \(0\)，要改成 \(-\infty\)。
void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	int t1=l,t2=mid+1;
	for(int i=l;i<=r;++i)
		if((t1<=mid&&a[t1].x<=a[t2].x)||t2>r){
			if(!a[t1].typ) B.add(a[t1].y,a[t1].x+a[t1].y);
			b[i]=a[t1++];
		}else{
			if(a[t2].typ) ans[a[t2].tm]=min(ans[a[t2].tm],a[t2].x+a[t2].y-B.sum(a[t2].y));
			b[i]=a[t2++];
		}
	for(int i=l;i<t1;++i) B.clear(a[i].y);
	for(int i=l;i<=r;++i) a[i]=b[i];
}
void solve(bool t1,bool t2){
	for(int i=1;i<=n+m;++i){
		a[i]=t[i];
		if(t1) a[i].x=N-a[i].x;
		if(t2) a[i].y=N-a[i].y;
	}
	cdq(1,n+m);
}

P4390 [BalkanOI2007] Mokia 摩基亚

同样的三维偏序，只不过查询的时候改成了二维查询。把所有的询问一拆四，CDQ 分治的时候根据种类判断即可。

void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	int t1=l,t2=mid+1;
	for(int i=l;i<=r;++i)
		if((t1<=mid&&a[t1].x<=a[t2].x)||t2>r){
			if(!a[t1].typ) B.add(a[t1].y,a[t1].val);
			b[i]=a[t1++];
		}else{
			if(a[t2].typ==1) ans[a[t2].val]+=B.sum(a[t2].y);
			else if(a[t2].typ==2) ans[a[t2].val]-=B.sum(a[t2].y);
			b[i]=a[t2++];
		}
	for(int i=l;i<t1;++i) if(!a[i].typ) B.add(a[i].y,-a[i].val);
	for(int i=l;i<=r;++i) a[i]=b[i];
}

int main(){
	read(),n=read()+1;
	int tm=0;
	while(1){
		int op=read();
		if(op==3) break;
		if(op==1) a[++tot]={read()+1,read()+1,read(),0};
		else{
			++tm;
			int x1=read()+1,y1=read()+1,x2=read()+1,y2=read()+1;
			a[++tot]={x2,y2,tm,1};
			a[++tot]={x1-1,y1-1,tm,1};
			a[++tot]={x1-1,y2,tm,2};
			a[++tot]={x2,y1-1,tm,2};
		}
	}
	cdq(1,tot);
	for(int i=1;i<=tm;++i) write(ans[i]);
	return fw,0;
}

P4093 [HEOI2016/TJOI2016] 序列

设 \(f_i\) 为以第 \(i\) 项结尾的子序列最长长度，则转移方程为 \(f_i=\max_{j<i}\{f_j\}+1\)，前提是 \(a_{j\max}\le a_i\land a_j\le a_{i\min}\)。加上项从小到大转移，这就是三维偏序。考虑 CDQ。

具体而言，将 \([l,\mathit{mid}]\) 按照其能最大变成的值 \(a_{i\max}\) 排序，\([\mathit{mid}+1,r]\) 就按照原本的 \(a_i\) 排序。在扫描 \([l,r]\) 的过程中，把第三维加到树状数组中，套路地统计即可。

注意用 \(\tt sort\) 就得用 \(\tt sort\) 的写法，不能再用归并排序的写法了。

void cdq(int l,int r){
	if(l==r) return dp[l]=max(dp[l],1),void();
	int mid=(l+r)>>1;
	cdq(l,mid);
	for(int i=l;i<=r;++i) p[i]=i;
	sort(p+l,p+mid+1,[&](int x,int y){return a[x].mx<a[y].mx;});
	sort(p+mid+1,p+r+1,[&](int x,int y){return a[x].x<a[y].x;});
	int k=l;
	for(int i=mid+1;i<=r;++i){
		while(k<=mid&&a[p[k]].mx<=a[p[i]].x)
			B.add(a[p[k]].x,dp[p[k]]),++k;
		dp[p[i]]=max(dp[p[i]],B.sum(a[p[i]].mn)+1);
	}
	for(int i=l;i<=mid;++i) B.clear(a[i].x);
	cdq(mid+1,r);
}

int main(){
	n=read(),m=read();
	for(int i=1,x;i<=n;++i) a[i]={x=read(),x,x};
	for(int i=1,x,y;i<=m;++i){
		x=read(),y=read();
		a[x].mx=max(a[x].mx,y);
		a[x].mn=min(a[x].mn,y);
	}
	cdq(1,n);
	printf("%d\n",*max_element(dp+1,dp+n+1));
	return 0;
}

意犹未尽的感觉。

整体二分

好一个二分！

起因是这样的，遇到有一部分能用二分解决的问题时，我们就可以用 \(O(n\log n)\) 的复杂度解决。但如果是多次询问，每次询问的还是不同区间，直接二分就变成了 \(O(n^2\log n)\)，还不如暴力。当然可以用树套树做，但是没有必要。要么用主席树，但我们还没学。所以整体二分就是用来解决这个问题的。

整体二分同样是离线算法。所谓整体二分，其 “整体” 就体现在把询问和原序列一起二分。比如，我用 \(\operatorname{solve}(l,r,L,R)\) 表示我的序列二分到 \([l,r]\) 这个区间，同时我的询问二分到 \([L,R]\) 这个区间，我保证这个区间内询问的答案在我二分到的这个序列区间里面。如果你把这句话消化了，那么我们就可以开始考虑怎么处理使得这个要求满足。

经典例题

静态区间 k 小值（P3834 【模板】可持久化线段树 2）

这题原本是主席树的板题，但也是整体二分的板题。定义 \(\operatorname{solve}(l,r,L,R)\) 表示已知询问 \([L,R]\) 的答案在 \([l,r]\) 中，考虑如何分治下去。

因为我们解决的是 “区间内小于 \(x\) 的数有多少个” 的问题，贡献是可加的，我们把它们看作是值域在 \((-\infty,l)\) 和 \([l,\mathit{mid}]\) 两部分的和，前者已经在之间的分治中求出，后者可以用树状数组做。利用树状数组维护区间和，然后对于每个询问 \(O(\log n)\) 判断分给哪个区间。

剩下的就是个板子。

void solve(int l,int r,int L,int R){
	if(L>R) return;
	if(l==r){
		for(int i=L;i<=R;++i) ans[Q[i].id]=a[id[l]];
		return;
	}
	int mid=(l+r)>>1,p=L-1,q=R+1;
	for(int i=l;i<=mid;++i) B.add(id[i],1);
	for(int i=L,sm;i<=R;++i){
		sm=B.sum(Q[i].r)-B.sum(Q[i].l-1);
		if(sm>=Q[i].k) tmp[++p]=Q[i];
		else Q[i].k-=sm,tmp[--q]=Q[i];
	}
	for(int i=l;i<=mid;++i) B.add(id[i],-1);
	for(int i=L;i<=p;++i) Q[i]=tmp[i];
	for(int i=q;i<=R;++i) Q[R+q-i]=tmp[i];
	solve(l,mid,L,p),solve(mid+1,r,q,R);
}

其中 \(\mathit{id}_i\) 是 \(a_i\) 按照大小排序后的下标。其实如果这个题的值域在树状数组承受范围之内，就不需要 \(\mathit{id}\) 数组，直接把原数组排一下序就可以了。其实主要还是板子。

动态区间 k 小值（P2617 Dynamic Rankings）

加了修改也是一样，不过这次把原序列和询问/修改都加到一个结构体里面，整体二分的时候一并处理。因为我们分的是值域，对询问的时间顺序是没有要求的。所以我们把询问按照时间轴排序之后，考虑如何把修改也放进去。而修改又可以拆成是在 \(\mathit{pos}\) 的位置上删除了一个 \(a_{\mathit{pos}}\)，又增加了一个 \(x\)，所以也可以放进去二分。具体而言，仍像刚才那样把树状数组处理到 \([l,\mathit{mid}]\) 这个集合，然后按照时间顺序处理修改和询问即可。

void solve(int l,int r,int L,int R){
	if(L>R) return;
	if(l==r){
		for(int i=L;i<=R;++i)
			if(Q[i].op)
				ans[Q[i].id]=b[l];
		return;
	}
	int mid=(l+r)>>1,p=L-1,q=R+1;
	for(int i=L,sm;i<=R;++i)
		if(Q[i].op){
			sm=B.sum(Q[i].r)-B.sum(Q[i].l-1);
			if(sm>=Q[i].k) tmp[++p]=Q[i];
			else Q[i].k-=sm,tmp[--q]=Q[i];
		}else{
			if(Q[i].k<=b[mid]){
				B.add(Q[i].l,Q[i].id);
				tmp[++p]=Q[i];
			}else tmp[--q]=Q[i];
		}
	for(int i=L;i<=p;++i)
		if(!tmp[i].op)
			B.add(tmp[i].l,-tmp[i].id);
	for(int i=L;i<=p;++i) Q[i]=tmp[i];
	for(int i=q;i<=R;++i) Q[i]=tmp[R+q-i];
	solve(l,mid,L,p),solve(mid+1,r,q,R);
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		b[++cnt]=a[i];
		Q[++tot]={0,i,0,a[i],1};
	}
	for(int i=1,l,r,k;i<=m;++i){
		string s;
		cin>>s;
		if(s=="C"){
			cin>>l>>r;
			b[++cnt]=r;
			Q[++tot]={0,l,0,a[l],-1};
			Q[++tot]={0,l,0,r,1};
			a[l]=r;
		}else{
			cin>>l>>r>>k;
			Q[++tot]={1,l,r,k,++q};
		}
	}
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	solve(1,cnt,1,tot);
	for(int i=1;i<=q;++i) cout<<ans[i]<<'\n';
	return 0;
}

P1527 [国家集训队] 矩阵乘法

换成二维树状数组即可。

void solve(int l,int r,int L,int R){
	if(L>R) return;
	if(l==r){
		for(int i=L;i<=R;++i) ans[Q[i].id]=a[l].c;
		return;
	}
	int mid=(l+r)>>1,p=L-1,q=R+1;
	for(int i=l;i<=mid;++i) B.add(a[i].x,a[i].y,1);
	for(int i=L,sm;i<=R;++i){
		sm=B.sum(Q[i].x1,Q[i].y1,Q[i].x2,Q[i].y2);
		if(sm>=Q[i].k) tmp[++p]=Q[i];
		else Q[i].k-=sm,tmp[--q]=Q[i];
	}
	for(int i=l;i<=mid;++i) B.add(a[i].x,a[i].y,-1);
	for(int i=L;i<=p;++i) Q[i]=tmp[i];
	for(int i=q;i<=R;++i) Q[i]=tmp[R+q-i];
	solve(l,mid,L,p),solve(mid+1,r,q,R);
}

P7424 [THUPC2017] 天天爱射击

正难则反，考虑每块木板是被哪个子弹打碎的。题目显然就被转化成了一个区间 \(k\) 小值的问题，可以用整体二分做。

注意不能写 pos[read()]=i，因为一个位置可能有多个数。所以读的时候就正常写 pos[i]=read()，把 \(\mathit{pos}\) 数组看成存储 \(i\) 点下标的数组，\(\operatorname{solve}\) 函数里面稍微改动一下即可。

统计答案的时候有不同的统计方法，如果正常统计的话需要多一枚子弹，因为有的木板可能自始至终都没被打碎，多一枚子弹的目的是把多出来的这部分贡献统计到这枚虚弹而不是正常的 \(m\) 颗子弹里。或者也可以像我一样的写法，判断当前子弹的剩余耐久度是不是只剩下了 \(1\)。

void solve(int l,int r,int L,int R){
	if(L>R) return;
	if(l==r){
		for(int i=L;i<=R;++i)
			if(Q[i].s==1&&Q[i].l<=pos[l]&&pos[l]<=Q[i].r)
				++ans[l];
		return;
	}
	int mid=(l+r)>>1,p=L-1,q=R+1;
	for(int i=l;i<=mid;++i) B.add(pos[i],1);
	for(int i=L,sm;i<=R;++i){
		sm=B.sum(Q[i].r)-B.sum(Q[i].l-1);
		if(sm>=Q[i].s) tmp[++p]=Q[i];
		else Q[i].s-=sm,tmp[--q]=Q[i];
	}
	for(int i=l;i<=mid;++i) B.add(pos[i],-1);
	for(int i=L;i<=p;++i) Q[i]=tmp[i];
	for(int i=q;i<=R;++i) Q[R+q-i]=tmp[i];
	solve(l,mid,L,p),solve(mid+1,r,q,R);
}

P4602 [CTSC2018] 混合果汁

很有意思的一道题，回味无穷。

考虑整体二分，在当前询问区间 \([L,R]\) 中二分答案，二分最小美味值。设二分出的最小美味值是 \(\mathit{mid}\)，那我们就只考虑美味值大于 \(\mathit{mid}\) 的果汁。在这些果汁中肯定优先考虑价格最低的，把价格最低的拉满之后再依次考虑。这个贪心显然是正确的。

考虑怎么维护果汁信息。为了实现 “优先考虑价格最低”，我们可以开两个树状数组，分别维护体积和总价，其中总价就是体积乘单价。这样做是为了维护方便维护前缀，充分利用了树状数组的特性。

然后是非常巧妙的一点：我们每次把美味度小于等于 \(\mathit{mid}\) 的果汁从树状数组中删除，这样就能做到前缀只包含美味度大于 \(\mathit{mid}\) 的果汁；查前缀的时候直接查询，再加上当前的果汁计算贡献。把小朋友按照能否负担起价格二分，然后这题就差不多了。

标签：二分,mathit,int,t2,mid,t1,++,CDQ,&&
From： https://www.cnblogs.com/laoshan-plus/p/18679772

相关文章

  • Atcoder ABC389E Square Price 题解 [ 绿 ] [ 二分 ] [ 贪心 ]
    SquarePrice：垃圾卡精度，垃圾卡精度，垃圾卡精度，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人。把ll改__int128前WA*22，改__int128直接AC了，难评。抛开卡精度这题还是挺好的。暴力先考虑暴力思路，显然暴力应该这么打：把所有物品全丢进优先队列......
  • 学习报告-论对“整体二分”的新理解
    学习报告-论对“整体二分”的新理解二分我们都知道，我们一般会通过二分具有单调性的答案来找到一个最接近某个点的答案。我们可能在以后的学习中遇到一些题，其答案是具有单调性的，但是如果让你在下面构造一个序列，或者构造一些答案，这些答案是无法二分的，只能“根据答案求过程”。然而......
  • 整体二分
    个人认为就是爆改cdq。大体思路和cdq相同：每次递归传入操作集合op和区间\([l,r]\)，表示修改操作的修改位置以及查询操作的答案都位于\([l,r]\)内$；统计左区间修改对全区间查询的贡献；判断查询应下放到左右哪个区间；分割操作至左右两区间例题海亮OJ题单P3834【模板......
  • 二分
    1.解释其实这个东西吧，是分治的分支优点：时间复杂度低，十分简单，方便写，适用绝大多数题目缺点：总有人眼瞎写错（）2.步骤1.在序列中确定中间数2.判断这数是不是，\(<\)的话去左边找，否则去右边找3.重复步骤直到中间数是要求的数字3.例题题目:洛谷P1873方法:朴素算法查找肯定超时，......
  • 二分查找算法的3种模板-PYTHON
    classbinary_search(object):def__init__(self,nums,target):self.nums=numsself.target=targetdefbinary_search_template_1(self):iflen(self.nums)==0:return-1l,r=0,len(self.nums)-1......
  • 搜索与图论（三）-最小生成树(Prim、Kruskal)和二分图(染色法、匈牙利法)
    目录一、最小生成树1.Prim算法 2.Kruskal算法二、二分图  1.判断二分图--染色体法 2.求二分图最大匹配--匈牙利算法一、最小生成树1.Prim算法         分为朴素Prim算法和堆优化Prim算法。写法和dijikstra算法类似，堆优化过程也类似，可类比学习。首......
  • day01 704. 二分查找&&27. 移除元素
    二分查找（search方法）publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;intmid;while(left<=right){mid=(left+right)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){left=mid+1;}else{right=mid-1;}}retur......
  • 【LeetCode 刷题】二分搜索
    此博客作为《代码随想录》的学习笔记，主要内容为二分搜索法及相关题目解析。文章目录704.二分查找35.搜索插入位置34.在排序数组中查找元素的第一个和最后一个位置69.x的平方根367.有效的完全平方数以下所有二分法算法均基于左闭右闭区间704.二分查找LeetCode......
  • 树状数组【单点修改+区间查询】+二分
    https://codeforces.com/gym/580226/problem/H#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definelowbit(x)x&(-x)usingll=longlong;usingpii=pair<int,int>;constdoublePI=acos(-1);constintN=2e5......
  • 算法-在数组中获取制定值的索引值-php（二分法）
    算法-在数组中获取制定值的索引值-php（二分法）<?php/***代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可***@paramnumsint整型一维数组*@paramtargetint整型*@returnint整型*/functionsearch($nums,$target){//......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99