分治即”分而治之”,根据不同的数据范围选用不同的处理方法.
CDQ分治
看这个视频了解一下三维CDQ是怎么运作的.
然后过一个板子题(陌上花开).
正常的二位偏序是使用排序降掉一维,使用线性结构(树状数组,线段树等)降掉一维.
假如碰到三维偏序,就需要想办法再降一维,这个时候CDQ应运而生.
注意 :CDQ分治只能解决元素不同的情况,否则需要进行离散化(去重)再算贡献,因为贡献是相同元素也可以给自己有贡献.
网上有n维偏序的板子能直接抄.
根号分治
看这个博客
手工分治
手动判断数据范围,手动选择合适的算法.举例:
乐高墙