CDQ小结

其实就是扩展归并排序。
适用于处理偏序问题。

算法

对于三维或以上偏序,我们采用CDQ分治。
第一个思想是排序。
先使第一维有序,然后将区间分成两半后两边各自按第二维排序,可以保证左一半的第一维小于右一半。
然后就可以对左右做类似归并排序的事情,用左边更新右边的答案。
更新过程中用树状数组保证第三维有序。

时间复杂度\(O(logn*nlogn)=O(nlog^2n)\)


技巧

大概就是可以把一些二位数点问题变化为横纵坐标,时间的三维偏序问题处理。

对于高维偏序可以CDQ套CDQ,但是5维以上还不如K-D tree和n^2枚举。


题目

一.洛谷P4169 [Violet]天使玩偶/SJY摆棋子
因为是曼哈顿距离,只考虑\(x\leq qx,y\leq qy\) 的点中 \(x+y\) 的最大值,然后旋转坐标系就可以统计到所有点。
我们将一个询问拆成了四个偏序问题,CDQ即可。


二.洛谷P5459 [BJOI2016]回转寿司
统计前缀和\(A_i\),然后前缀和做差统计区间
保证\(l<r,L<A_r-A_{l-1}<R\)
那么可以转化为\({A_{l-1}+L<A_r<A_{l-1}+R}\)
但其实可以发现\(l<r\)并没有什么用,因为前缀和是单调的
所以其实可以类似二维偏序\(O(nlogn)\)
或者采用不排序直接归并的CDQ实现

上一篇:浅谈CDQ分治三维偏序(傻瓜详解)


下一篇:CDQ分治学习笔记