Marser的线段树分治题单

线段树分治是一种处理动态修改和询问的离线算法。通过将某一元素的出现时间段在线段树上保存，我们可以dfs遍历整棵线段树，运用可撤销数据结构维护来得到每个时间点的答案。 一般来讲，线段树二分会与可撤销并查集相结合。同时，如果用于维护的数据结构是线性基等空间复杂度可接受的算法，也可以在每一层保存一遍，用以更新。 同时，对于部分特殊的问题，需要根据已有的性质动态求出出现区间，再进行处理，相应的dfs顺序也要更改。 总而言之，线段树分治是一种优秀的离线算法，可以简化很多复杂的操作，在高级别考试中也有很多应用。 [P4588](https://www.luogu.com.cn/problem/P4588) 最基础的例题，可以通过此题熟悉时间线段树的操作。 [P5787](https://www.luogu.com.cn/problem/P5787) 最常见的模版题，需要了解二分图的充要条件：图上不存在奇环。 [P4219](https://www.luogu.com.cn/problem/P4219) 用可撤销并查集维护联通块大小，在dfs过程中更新，避免写LCT维护虚子树大小。 [CF938G](https://www.luogu.com.cn/problem/CF938G) 由于异或的优秀性质，可以将看上去复杂的图论问题转化成关于每条边的线性基上问题。由于不支持撤销，我们在当前dfs栈中的每个节点上保存一份副本，供下一步的处理，最多保存$\log n$个，可以接受。 [P3733](https://www.luogu.com.cn/problem/P3733) bitset实现线性基，余下方法与CF938G类似。 [CF603E](https://www.luogu.com.cn/problem/CF603E) 每条边成为最优解的范围是一个连续区间，可以在dfs过程中维护一个堆，不断确定各条边的出现范围，注意此时要改变dfs的顺序。 [P4585](https://www.luogu.com.cn/problem/P4585) 用可持久化Trie辅助维护，避免了树套树的毒瘤做法。注意这种树形数据结构都是支持撤销的。 [CF1140F](https://www.luogu.com.cn/problem/CF1140F) 把点看成二分图上的一条边，每个联通块的贡献就是左侧节点数乘右侧节点数，用可撤销并查集维护即可。 [CF576E](https://www.luogu.com.cn/problem/CF576E) 没有给定每条边的出现区间，但我们发现每个染色区间只有两种可能，只要假定一种成立，进行check即可。