一点小疑问
查看原帖
一点小疑问
782808
Nazale_楼主2024/7/31 07:50

正常在做cdq时,不应该在外部保证一维偏序,再在分治过程中排序保证第二层偏序,才能用树状数组快速地做一个类似二维数点的问题吗?但是为什么这题的卡常技巧说暂存这个数组再复制只是按时间排序了却还是对的?求解答

bool cmp1(ele x,ele y){
	return x.x<y.x;
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	cdq(l,mid);  cdq(mid+1,r);
//	sort(ue+l,ue+1+mid,cmp1);
//	sort(ue+1+mid,ue+1+r,cmp1);
	int i=l,j=mid+1;
	int k=l;
	while(j<=r){
		while(i<=mid && ue[i].x<=ue[j].x){
			if(ue[i].type&1) bit.add(ue[i].y,ue[i].s);
			tmp[k++]=ue[i++];
		}
		if(ue[j].type==2) e[ue[j].id].res=min(e[ue[j].id].res,ue[j].s-bit.qry(ue[j].y));
		tmp[k++]=ue[j++];
	}
	for (int k=l;k<i;k++){
		if(ue[k].type&1) bit.clr(ue[k].y);
	}
	while(i<=mid) tmp[k++]=ue[i++];
	for (int i=l;i<=r;i++){
		ue[i]=tmp[i];
	}
}
2024/7/31 07:50
加载中...