Marser的整体二分题单
题单介绍
整体二分是一种优秀的离线算法。对于可二分答案的问题，我们可以采用整体二分的方法处理多组询问。整体二分的思想非常巧妙，能够替代很多复杂的数据结构，代码也十分好写，是考场上的一大利器。
题单中有一些题的做法不唯一，也可以使用树套树之类的大数据结构解决。
[P3527](https://www.luogu.com.cn/problem/P3527) 基础的整体二分，用树状数组维护区间和即可。
[P4602](https://www.luogu.com.cn/problem/P4602) 用线段树维护已经加入的元素，复杂度似乎比较可靠，详见[蒟蒻的题解](https://www.luogu.com.cn/blog/Marser/solution-p4602)。
[P1527](https://www.luogu.com.cn/problem/P1527) 用二维树状数组维护，也是一道经典题了。
[P3242](https://www.luogu.com.cn/problem/P3242) 把问题放到了树上，树链剖分解决，码量可能比较大。
[P3250](https://www.luogu.com.cn/problem/P3250) BIT动态维护树上差分，比较清真的一道题。
[CF1100F](https://www.luogu.com.cn/problem/CF1100F) 用类似猫树的方法预处理从中间开始向两边的线性基，直接处理跨越区间中点的询问，递归处理两边的询问，可能不太像正宗的整体二分。
[P5163](https://www.luogu.com.cn/problem/P5163) 神仙题，用可撤销并查集维护此前缩点的结果，每次加入区间中出现时间小等于mid的边，在缩点后的图上跑tarjan来进行check，相当毒瘤。如有疑问，欢迎访问[蒟蒻的题解](https://www.luogu.com.cn/blog/Marser/solution-p5163)。
[P2617](https://www.luogu.com.cn/problem/P2617) 带修改区间k小值，可以用整体二分代替树状数组上主席树。
[P3332](https://www.luogu.com.cn/problem/P3332) 树套树经典题，整体二分也是相当不错的做法。