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

考 XCPC 训练赛的时候见到的题，赛时拼尽全力无法战胜，故写一篇题解记录一下。

下面两段是我赛时的想法，都是错的我太菜了，不感兴趣的可以跳过。

先给出一个大部分人都会考虑的做法：将 $a$ 拆位，对于每一位分别维护。发现与操作相当于是区间赋 $0$，赋值操作是单点赋值。查询操作就是从高位往低位扫，如果该位只有一个 $0$，显然删除这个 $0$ 能使答案最大化。复杂度 $O(n\log V\log n)$。显然过不了。

考虑优化，我们运用势能分析，发现每一位只会有 $O(n+q)$ 个 $1$，于是考虑使用神秘集训队科技压位 Trie，复杂度是 $O(n\log V \log_{64} n)$。发现显然还是过不了。过不了你在这哔哔什么

上面都是假做法，接下来讲真做法。

发现把每一位都拆出来不可做，因为这样至少会有一个 $\log V$，因此考虑将所有位统一处理。

还是线段树，考虑在线段树上维护这个区间的与和，同时维护这个区间内是否只有一个 $0$，本质上就是将 $\log$ 棵线段树上的数据压到了一棵线段树内。

发现与和这个信息是平凡的，接下来讨论区间 $0$ 信息如何维护。

考虑合并，可以分讨这个 $0$ 出现在了左儿子还是右儿子。至于区间修改操作，需要讨论两种情况。

信息已经维护好了，那么可以直接查询区间信息，找最高的只有一个 $0$ 的那一位，然后线段树二分找出这个位置，把这个位置刨去就能得到答案了。

代码写的有点丑，就不放了。想看的自己点进来看。