上午的学习学会了整体二分，下午学了cdq分治 发现了二者的区别： 整体二分的主体是在不断地二分答案（把所有询问二分），，而cdq分治则是在不断地二分操作。 当然同样的,cdq分治的复杂度也是与区间长度正相关. 我们定义函数Solve(l,r)可以得到操作l,r的结果 cdq分治的实现过程:
主要过程:
Step1.将所有操作按照某个关键字排序.(不一定是读入顺序.) Step2.二分操作.对于操作区间[l,r],mid为按操作出现时间排序后找到的mid.我们让[l,mid]是按照操作出现时间排序的,而[mid+1,r]仍旧是按着Step1中的关键字排序. Step.3首先求解[l,mid],在根据递归求解后的数据来求解[mid+1,r]中的操作. Step.4递归执行上述2,3操作直到整个题目得以求解.
我们可以看到,[l,mid]中的操作一定对[mid+1,r]中的操作是没有任何影响的,因此这样子递归操作下去正确性显而易见. 而求解的过程根据不同的题当然也是不同的,就拿陈丹琦论文中的那两个题(cash和mokia)来说,cash的本质是dp,因此求解过程就是更新f数组,而mokia就是模拟出操作就行了. cdq分治或许在时间上并不比那些高级数据结构优越很多,但是它的代码复杂度的确要低很多(虽然我傻逼写代码一直比较长但是还是比我的那些高级数据结构短,不要说树套树,就算是普通的一棵sbt都比cdq长了= =看见这里的神犇请不要嘲讽我QAQ毕竟我太弱了) 具体题目单独写题解.
当你感到悲哀痛苦时，最好是去学些什么东西。
