Marser的整体二分题单

整体二分是一种优秀的离线算法。对于可二分答案的问题,我们可以采用整体二分的方法处理多组询问。整体二分的思想非常巧妙,能够替代很多复杂的数据结构,代码也十分好写,是考场上的一大利器。
题单中有一些题的做法不唯一,也可以使用树套树之类的大数据结构解决。

P3527 基础的整体二分,用树状数组维护区间和即可。
P4602 用线段树维护已经加入的元素,复杂度似乎比较可靠,详见蒟蒻的题解。
P1527 用二维树状数组维护,也是一道经典题了。
P3242 把问题放到了树上,树链剖分解决,码量可能比较大。
P3250 BIT动态维护树上差分,比较清真的一道题。
CF1100F 用类似猫树的方法预处理从中间开始向两边的线性基,直接处理跨越区间中点的询问,递归处理两边的询问,可能不太像正宗的整体二分。
P5163 神仙题,用可撤销并查集维护此前缩点的结果,每次加入区间中出现时间小等于mid的边,在缩点后的图上跑tarjan来进行check,相当毒瘤。如有疑问,欢迎访问蒟蒻的题解。
P2617 带修改区间k小值,可以用整体二分代替树状数组上主席树。
P3332 树套树经典题,整体二分也是相当不错的做法。


  1. P3527 - [POI 2011] MET-Meteors
  2. P4602 - [CTSC2018] 混合果汁
  3. P1527 - [国家集训队] 矩阵乘法
  4. P4175 - [CTSC2008] 网络管理
  5. P3242 - [HNOI2015] 接水果
  6. P3250 - [HNOI2016] 网络
  7. CF1100F - Ivan and Burgers
  8. P5163 - WD与地图
  9. P2617 - Dynamic Rankings
  10. P3332 - [ZJOI2013] K 大数查询