CF1903D2 Maximum And Queries (hard version) 题解

· · 题解

建议先看 easy version 的题解。

注意到一个性质：当一个数被更新到拥有 $2^i$ 这一位之后，它的更低位目前一定都是 $0$。也就是说，后面遍历到更低位，希望它能有这个更低位 $2^j (j < i)$ 时，这个数消耗的代价为 $2^j$，是个相对确定的值。 x 另外你在做 easy version 的时候可能会发现 $a_i$ 的范围异常的小（不大于 $10^6 < 2^{20}$）这一点在 easy version 里似乎并没有用到。 由此可以想到根据答案的最高位 $2^w$ 进行讨论。对每个询问求出答案的最高位是简单的，预处理每一位的代价即可。 如果 $w\geq 20$，所有数经过第一次变换后，都变成了 $2^w$，设剩下的操作次数为 $c$，那么最终答案为 $2^w + \displaystyle\lfloor \frac{c}{n}\rfloor$。 如果 $w\leq 19$，接下来我们按位贪心。假设目前答案为 $ans$，我们现在在贪的位是 $2^i$，剩余的操作次数为 $c$，那么我们现在需要知道的就是要把所有数都变得有 $ans + 2^i$ 中所有的位的最小代价是否不大于 $c$。考虑 $ans$ 到 $ans + 2^i$ 的增量。发生的变化有两类：第一类数 $x$，它在之前已经发生过变化，即 $x \& ans < ans$，那么本次操作它的代价为 $2^i$，需要在此前的贪心过程中维护这样的数的个数 $fik$。另一种产生代价的数 $y$ 满足 $y \& ans = ans$，但 $y \& (ans + 2^i) < (ans + 2^i)$ 即 $y$ 有 $ans$ 的所有位但没有 $2^i$ 这一位。设这样的数的个数为 $f$，总和为 $g$，根据 easy version 的贪心结论，这类数的总代价为 $f\times 2^i - g$。 以上总代价为 $fik\times 2^i + f\times 2^i - g$。怎么求出 $f$ 和 $g$？发现符合要求的数满足“某一位必须不存在，这一位之前的指定的若干位必须存在”，预处理时可以枚举不存在的位，剩下的是半个 FMT-or，即超集求和。注意到贪到 $2^i$ 可以加入 $ans$ 的时候，要更新剩余的操作次数和 $fik$。 启发：看到奇怪的数据范围一定要深入思考为什么是这样。~~如果赛后发现没什么道理的话就喷出题人。~~ [for reference only.](https://codeforces.com/contest/1903/submission/235188787)