离线算法学习笔记

· · 个人记录

线段树分治

离线算法的有很大一部分是通过将删除操作转化成撤销操作，线段树分治就是这样的算法。

简单的引入：在很多有修改操作的题目中，无非就是引入了一个时间轴的概念。每进行一次修改，就代表着时间轴的向后推进。有些时候，我们的修改操作是放一个物品，然后这个物品会对查询产生一定的贡献与影响。那么从这个物品出现的时间点 x 开始，其会影响到其消失时的时间点 y 之间所有时间都会产生影响。换言之，我需要将这个物品的影响，对于区间 [x,y] 所有询问进行覆盖。我们没有办法一个一个去覆盖，所以我们使用线段树的懒标记来完成这个覆盖操作，这就是线段树分治。

具体实现：以带删除并查集（支持删边连边，查询连通性）为例，我们对于时间轴建立一颗线段树,一个节点 [l,r] 对应维护时间 [l,r] 间，有那些边一直存在，对于一条边存在的时间区间 [x,y] ，我们想区间加一样找到完全覆盖就打懒标记。最后全局维护一个可撤销并查集，从线段树根节点开始进行先序遍历，到一个节点就把对应边加上，出去就把加上的边撤消了，到叶子就把对应的时间的询问给回答了。对于每一条边，拆分到线段树上至多拆分 \log{n} 个，一共就是要加 n\log{n} 条边，单次加边是 \log{n} ，整体复杂度为 n\log^2{n}。

总结一下，当看到一个物品产生贡献的是在区间出现，有消失的，在保证复杂度的情况下，可以使用这个算法。

CDQ 分治

不管是区间，还是其他的，当遇到给你一些限制，让你在满足限制的点中找答案的时候，CDQ 分治是很好的选择。

简单的引入：回想逆序对的归并排序求法，我们每次将当前均分，先将左右区间分别排好序，然后对于每一个处在右区间的数 x ，一边归并排序，一边计算左区间中有多少个大于 x 的数。之所以可以这样做，是因为左区间的下标一定是满足小于右区间的下标的，这样我们就先满足了一维限制。然后就可以把问题转换成只有一维的限制，从而简化问题，由于每一个左右都会被考虑到，所以我们得到了正确的答案。其实这里的归并排序已经有了 CDQ 分治的雏形，他就是简化限制条件的一个高效算法。

具体实现：类似于归并排序，先分别递归左右区间（视具体情况而定，假如右区间的信息需要用左区间的信息时，要先左，然后计算当前层的贡献，然后计算右边的贡献）。然后考虑左区间向右区间的答案进行贡献即可。

整体二分

有些时候，单个询问我们可以用二分在 O(n \log{n}) 的时间复杂度，但是多个问题每一个都需要二分的时候，时间复杂度就有了问题。然而，因为最开始的上下界一定，我们发现一个询问可能会多次询问到同一个 \text{mid}。那么对于每一个询问我们都计算了一次这个 \text{mid} 的答案，这很浪费，所以我们不妨把所有的询问一起进行二分，这样一个 \text{mid} 就只用计算一次了。

具体实现：将当前二分到的答案区间与询问的区间一起进行二分，取当前答案区间的 \text{mid} ，然后计算答案，然后将根据询问到的答案将所有询问分成两份，分别为答案在左区间，与答案在右区间的询问，依次二分下去，最终找到答案。