三维偏序整体二分？

基于整体二分的CDQ分治实现？

众所周知的是三维偏序可以使用整体二分解决，但是今天我研究了一下，发现这个整体二分并不是一般意义下的整体二分，而是CDQ分治的一种类似整体二分的实现。

一般而言，整体二分指的是平行二分答案，这里以区间第

k

小举例。

你的

solve(ql,qr,l,r)

指的是

ql,qr

的询问的答案属于

l,r

，并且二分答案，使用 BIT 维护。

但是在三维偏序（CDQ分治）中，你的整体二分二分的是一个阈值，小于的对大于的贡献，你的操作仅仅是将操作分组，而不是二分答案，所以三维偏序根本没有整体二分的写法，只是长得像整体二分的CDQ分治。

CPP

void solve(int ql,int qr,int l,int r){
	if(ql>qr)return;
	int mid=l+r>>1,cnt1=0,cnt2=0;
	for(int i=ql;i<=qr;i++){
		if(q[i].tp==1){
			if(q[i].y<=mid){
				q1[++cnt1]=q[i];
				add(q[i].z,1);
			}
			else q2[++cnt2]=q[i];
		}
		else{
			if(q[i].y<mid)q1[++cnt1]=q[i];
			else{
				q2[++cnt2]=q[i];
				ans[q[i].id]+=ask(q[i].z);
			}
		}
	}
	for(int i=1;i<=cnt1;i++)
		if(q1[i].tp==1)
			add(q1[i].z,-1);
	for(int i=1;i<=cnt1;i++)q[ql+i-1]=q1[i];
	for(int i=1;i<=cnt2;i++)q[ql+cnt1+i-1]=q2[i];
	if(l==r)return;
	solve(ql,ql+cnt1-1,l,mid);
	solve(ql+cnt1,qr,mid+1,r);
}//第一关键字x，第二关键字tp，tp=1插入，tp=2查询

我们根本没有在二分答案！而是二分一个阈值来计算答案，这一点和CDQ本质相同。

三维偏序整体二分？

文章操作

基于整体二分的CDQ分治实现？

相关推荐

评论

三维偏序整体二分？