整体二分 学习笔记

发布时间 2023-07-16 10:35:45作者: 383494

对多个答案同时二分。

每次将答案在 \([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\)(撤销原操作),新数值正常处理。