CDQ 分治

概述

CDQ 分治用分治的思想离线处理带时间维的偏序与数点问题。整体按第一维分治，递归处理左右两半后，专门统计左半的修改对右半的询问所产生的跨区间贡献：此时左右两部分各自已按第二维有序，于是一边归并、一边用树状数组维护第三维即可累计这部分答案，再清空树状数组回溯。它常用于三维偏序、动态逆序对、带修改的数点等问题，把一维用分治的时间轴替代，时间复杂度通常为 O(nlog^2 n)。给出归并统计跨区间贡献的核心实现，例题为洛谷 P3810 三维偏序。

参考资料

• CDQ 分治 - OI Wiki

简介

CDQ 分治 用分治处理带「时间维」的偏序与数点问题。按第一维分治，递归处理左右两半后，专门统计 左半对右半 的跨区间贡献：此时左右各自已按第二维有序，归并的同时用树状数组维护第三维即可。常用于三维偏序、动态逆序对等，时间复杂度通常为 $O(n\log^2 n)$。

实现

349 Bcpp

void cdq(int l,int r)
{
	if(l==r)return;
	cdq(l,mid);
	cdq(mid+1,r);
	int p1=l,p2=mid+1;
	for(int i=l;i<=r;i++)
	{
		if(p1<=mid&&(p2>r||a[p1].y<=a[p2].y))
		{
			b[i]=a[p1++];
			bit.add(b[i].z,1);
		}
		else
		{
			b[i]=a[p2++];
			ans[b[i].id]+=bit.sum(b[i].z);
		}
	}
	for(int i=l;i<=mid;i++)bit.add(a[i].z,-1);
	for(int i=l;i<=r;i++)a[i]=b[i];
}

例题

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

有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j\leq a_i$ 且 $b_j\leq b_i$ 且 $c_j\leq c_i$ 且 $j\ne i$ 的 $j$ 的数量。

对于 $d\in[0,n)$，求 $f(i)=d$ 的数量。