题解：P14188 [ICPC 2024 Hangzhou R] Barkley III

· · 题解

询问相当于查询最高的，区间中只有一个数该位为 0 的位置，以及这个数的位置。如果没有这样的位，删掉任何数答案都不会变；否则删掉最高的这样的位对应的那个数，能使答案的这一位从 0 变成 1。

怎么做？线段树维护区间的两个值 a,b，其中 a 代表这个区间中，哪些位“每个数在这一位都是 1”（容易发现等价于区间 \operatorname{and}），b 代表这个区间中，哪些位“恰有一个数在这一位是 0”。

考察 update 怎么写，容易发现如果对于大区间，恰有一个数在某一位是 0，一定是两个子区间中某一个恰有一个 0，另一个全是 1。因此，我们有：

\begin{cases}fa_a=ls_a \operatorname{and} rs_a\\fa_b=(ls_a \operatorname{and} rs_b)\operatorname{or}(ls_b \operatorname{and} rs_a)\end{cases}

所有修改容易通过 tag 处理，区间长度是 1 的时候要特殊处理。

查询时，找到这个区间的 b 并取出最高位，然后可以借助区间与的信息在线段树上二分 “[l,r] 内第一个在某一位是 0 的数的位置” 。得到位置后把两边区间的区间与 \operatorname{and} 起来即可。