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

Binah_cyc · 2025-10-15 09:45:51 · 题解

考 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 出现在了左儿子还是右儿子。至于区间修改操作，需要讨论两种情况。

• 如果修改的不是元区间，则这一位满足条件需要满足与的是 1 且这一位本身满足条件，因为与 0 就会直接被赋成 0。所以直接与上修改的 x 即可。
• 如果修改的是元区间，因为区间长度只有 1，所以只要这一位是 0 那就恰好有 1 个 0。故不论原来是 0 还是与了 0 这一位都会变成 0。所以可以或上修改的 x 按位取反的结果。

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

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