CDQ分治小结

CDQ分治特别之处：时间

CDQ分治分的是时间。 然而。 时间又怎么了。 我们可以知道：时间上，后面的时间不能为前面的时间做贡献（只要你不站在上帝视角） 所以当且仅当 i<j 时， ansi→ansj 所以CDQ分治主要是这样做

void CDQ(l,r) { int mid=(l+r)>>1;//(l+r)/2 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) 题目示例：三维偏序