CDQ 分治

[Ir1d]

https://oi-wiki.org/misc/cdq-divide/

[MoveCloudROY]

CDQ和树套树的关系怎么说。。

[Xarfa]

树套树是模拟整个过程,而CDQ是判断整个过程。树套树空间大,CDQ空间小。树套树强制在线,CDQ离线。树套树有一定的范围,而CDQ的范围是你单个变量的最大值 (如 int64)

[WhenMelancholy]

_old driver tree_ 是想斜体然后没有被成功渲染吗?

[yongding-tao]

太棒了,讲得很清楚,网上的资料参差不齐,当初学的时候只学了第一种,但总觉得未理解,现在才搞清楚

[yzy-1]

这个 markdown 是咋得了？

[Enter-tainer]

@yzy-1 可以截图描述一下你的问题吗

[fususu654]

为什么是三类不应该是四类吗？

[fususu654]

还有啊，三维偏序是三个属性吧qwq

[lijinrui299792458]

@kaebkcuB
还有啊，三维偏序是三个属性吧qwq

这里的三个属性相当于是 i,a_i,b_i 吧

[xiachi00]

一般的cdq分治应该可以优化到nlogn吧 solve(l, r)最后的sort可以归并O(n)处理

[yggdyy]

城市建设那道题的解题思路中“对于一条边来讲”之下分出了两种情况，其中负无穷（第二种情况）中“而他未出现在树中”似乎应当改为“而他出现在了树中”
当然也可能是我的问题，

[383494]

这个用 set 维护连续的区间的技巧也被称之为 ...

“被称之为”是不是有语病

[ThisisXXZ]

现在在学 NLP，逛大佬陈丹琦 homepage 的时候无意间翻到论文，才知道当初学的 CDQ 分治就是她本人。。。跪了

[HDZsuper]

我在cs224n的网课上看到CDQ大佬作为助教讲课了

[visla-maxiangxiang]

CDQ可以用图的进行理解:

1. 把指标都看作图上的结点的id。2. 结点与结点之间存在依赖关系，用边表示，于是就构成了一个有向无环图G。3. 将图G划分成两个部分G1-->G2，也就是G2中的结点单向依赖G1中的结点。4. 递归计算G1中的结点的中的值，此时G1中的值为最终值。5. 利用G1更新G2，但此时G2结点中的值并不是最终值，而只是仅考虑G1与G2之间依赖关系而得到的中间值。6. 递归调用算法更新G2中结点的值，此时G1、G2中所有结点的值都为最终值。

• 算法递归到图中只包含一个结点的情形时返回。
• 算法需要保障要计算的量具有reduce性，如求最小值操作就有reduce性质：min(a,b,c,d)=min(min(min(a,b),c),d)，还有像加法、乘法、最大值操作都具有reduce性。
• 算法可以推广到更高维度上，只要能梳理好结点间的关系，构造出有向无环图即可。
• 对图的切分应该保障|G1|与|G2|尽可能接近，最差切分为每次切分都是|G1|=1，那么算法就退化成了按照拓扑顺序进行计算的动态规划。