2021/10/13(cdq分治)

嵌套cdq分治实际上是通过有序关系对数据进行标记筛选,在写多维度嵌套式cdq分治时这种感觉尤其明显,在分治过程中一层一层的根据不同排序关系在这次分治中筛选出满足条件的数据,来统合计算。

嵌套cdq分治中前k-1个维度都是通过排序然后标记,来筛选出对应满足相应限制的数据,最后一个维度则是根据排序,将数据分为左右两边,右边严格满足左边。(当然很多时候最后一维都是通过树状数组求之类的数据结构来处理,这时倒二维就可以使用该方法)

原文地址:https://www.cnblogs.com/komet/p/15404080.html