【笔记】整体二分

发布时间 2023-12-12 00:18:50作者: CloudWings

易错

在清除当前区间处理时的影响时,通常有两种做法:(下以区间第 \(k\) 小为例

若个数 res < 待查询第 k 小时,一般就有两种处理方法:

  1. k -= res,最后递归的时候直接清空 bit。
  2. k 不变,先递归右区间,清空 bit,再递归左区间。

正确性

在没有中途修改,或者可以认为所有的修改在查询前就完成了的情况下,这两种写法都对。但如果是边修改边查询,就只有第一种做法对。

对于第二种,考虑下述情况:有一次修改操作,在这一次处理时被放在 bit 上了。到下一次递归时,bit 初始就有值了,相当于在所有询问修改前,都做了这一次修改,但如果这次修改实际上是在某次查询之后,相当于后面的修改直接提前在 bit 上就影响了前面的一次查询,就错了。

一个例子:CF868F Yet Another Minimization Problem

  1. 第一种写法:AC
  2. 第二种写法:WA