本文主要是介绍CDQ小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
其实就是扩展归并排序。
适用于处理偏序问题。
算法
对于三维或以上偏序，我们采用CDQ分治。
第一个思想是排序。
先使第一维有序，然后将区间分成两半后两边各自按第二维排序，可以保证左一半的第一维小于右一半。
然后就可以对左右做类似归并排序的事情，用左边更新右边的答案。
更新过程中用树状数组保证第三维有序。
时间复杂度 O ( l o g n ∗ n l o g n ) = O ( n l o g 2 n ) O(logn*nlogn)=O(nlog^2n) O(logn∗nlogn)=O(nlog2n)
技巧
大概就是可以把一些二位数点问题变化为横纵坐标，时间的三维偏序问题处理。
对于高维偏序可以CDQ套CDQ，但是5维以上还不如K-D tree和n^2枚举。
题目
一.洛谷P4169 [Violet]天使玩偶/SJY摆棋子
因为是曼哈顿距离，只考虑 x ≤ q x , y ≤ q y x\leq qx,y\leq qy x≤qx,y≤qy的点中 x + y x+y x+y的最大值，然后旋转坐标系就可以统计到所有点。
我们将一个询问拆成了四个偏序问题，CDQ即可。
二.洛谷P5459 [BJOI2016]回转寿司
统计前缀和 A i A_i Ai，然后前缀和做差统计区间
保证 l < r , L < A r − A l − 1 < R l<r,L<A_r-A_{l-1}<R l<r,L<Ar−Al−1<R
那么可以转化为 A l − 1 + L < A r < A l − 1 + R {A_{l-1}+L<A_r<A_{l-1}+R} Al−1+L<Ar<Al−1+R
但其实可以发现 l < r l<r l<r并没有什么用，因为前缀和是单调的
所以其实可以类似二维偏序 O ( n l o g n ) O(nlogn) O(nlogn)
或者采用不排序直接归并的CDQ实现
这篇关于CDQ小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
