CDQ分治特别之处:时间
CDQ分治分的是时间。 然而。 时间又怎么了。 我们可以知道:时间上,后面的时间不能为前面的时间做贡献(只要你不站在上帝视角) 所以当且仅当
i<j
时,
ansi→ansj
所以CDQ分治主要是这样做
void CDQ(l,r)
{
int mid=(l+r)>>
1;
CDQ(l,mid);
CDQ(mid+
1,r);
Do something.
}
其中,我们设CDQ的复杂度为
T(i)
,Do something的复杂度用
D(i)
代替。 有
T(i)=2T(i2)+D(i)
当
D(i)=O(n)
时
T(i)=2T(i2)+O(1)=O(n log2n)
当
D(i)=O(n log2n)
时
T(i)=2T(i2)+O(n)=O(n log22n)
题目示例:三维偏序