整体二分 学习笔记

对多个答案同时二分。

每次将答案在 \([l, r)\) 中的询问按答案与 \(\text{mid}\) 的关系丢进两个 \([l, \text{mid})\) 和 \([\text{mid}, r)\) 的 std::vector 里，递归求解即可。

递归终止的条件：可能的答案区间长度为 \(1\)，此时答案唯一确定。

例题：带修区间 \(k\) 小

将修改和询问都打包成 struct op，塞进 vector 里，每次处理 \([l, r)\) 的操作。具体地，猜测 \(\text{mid}\) 为答案，每次遇到修改时如果此数 \(\lt \text{mid}\) 则将其视为 \(1\)，树状数组查区间和 \([\text{ask}.l, \text{ask}.r) = \text{num}\) \(\lt \text{ask}.k\) 则说明 \([\text{ask}.l, \text{ask}.r)\) 中第 \(k\) 大值 \(\ge \text{mid}\)，将此询问划分到右 vector 中，同时 \(k \leftarrow k-\text{num}\)（由于 \(\lt \text{mid}\) 的修改都被分走了）。左 vector 中的询问则不必。

对于修改，数状数组原数值若 \(\lt \text{mid}\) 则 \(-1\)（撤销原操作），新数值正常处理。