自动搬运

查看原文

来自洛谷，原作者为

	紊莫 ?？?

搬运于2025-08-24 23:12:30，当前版本为作者最后更新于2025-05-30 08:21:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先利用 bitset 建立线性基，对于一个查询，我们有如下贪心：

设当前位为 $i$，如果 $[i,m)$ 这些位都可以消成 $0$，那么退出，否则尽可能把 $i$ 这个位变成 $1$，然后 $i\gets i+1$。

正确性显然，暴力做复杂度是 $O(\frac{nm^2+qm^3}{\omega})$ 的。

暴力代码。

称线性基中能被我们随意操作的位为关键位。

那么我们只需要把线性基消元成关键位独立的形式就可以预处理所有后缀的关键位上的基中元素的异或和。

正解代码。

复杂度是 $O(\frac{nm^2+qm^2}{\omega})$。