自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:49:48，当前版本为作者最后更新于2023-06-20 18:11:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，我们需要明确胜负判断规则，防止把博和奕搞反，而关键句就是“博让奕，故为零博获胜”。

如果只考虑一次博弈，最初的异或和为零。每当遇到一个奕的数字，如果他选了，那么博必须想办法把这个数字抵消掉，即在后面寻找一个自己的数字集合，将它们取反（即选变不选，不选变选，最开始每个数字都不选）。

如果对于每一个奕的数字，博都能在后面找到抵消方案的话，博就获胜，如果存在一个找不到抵消方案，就是奕获胜。

奕获胜的方法就是，其它的数字都不选，只考虑这个数字选不选。而走到这里时，如果奕选或不选博在后面都有方法应对的话，将这两种方法异或能得出凑出该数的方案，与“找不到抵消方案”矛盾。

找子集异或起来等于给定数字就是异或线性基模板，于是我们能够成功解决一次博弈的胜负了，这样时间复杂度为 $O(n^2w)$，可以得到 $21$ 分。（$w=60$ 为二进制位数，下同）

然后你发现如果 $b_r=1$，那么 $[l,r]$ 一定是奕获胜（走到最后，为零就选，否则不选），于是子任务 $6$ 可以通过，子任务 $7$ 也可能通过，期望得分 $38\sim57$ 分。

要想得到更高的分，需要从单调性入手，本题的单调性在于固定右端点，左端点一定是前一段奕获胜，后一段博获胜，因为越往左越能找到一个“凑不出的”奕的数字，考虑求出 $L_r=\min\limits_{w(l,r)=0}l$，不存在则 $L_r=r+1$。

还有对于一个奕的数字，一定是前一段凑不出，后一段凑得出，这个就太明显了。

可以对于每一个奕的数字都二分找到最后一个凑不出的地方，用线段树或 ST 表套线性基维护。如果对于 $l$ 来说，最后一个凑不出的地方为 $r$，就有 $\forall x\in[l,r],L_x\ge l+1$，这里是一个区间最值操作，怎么做都可以。

求出 $L_x$ 之后，我们只需要扫右端点，每次对区间 $[1,L_r-1]$ 增加 $1$，然后 $[l,r]$ 的区间和就是答案，这里因为操作简单只需要使用树状数组，瓶颈在于线段树或 ST 表套线性基，为 $O(nw^2\log n+q\log n)$，不过特殊性质可以只维护 $b_i=0$ 的，忽略不计，能通过子任务 $1\sim 7$，期望得分 $80$ 分。

上面都不是难点，我们需要优化求 $L_x$ 的过程。

从右往左扫，扫到 $l$ 时，如果 $b_l=1,(l,r]$ 凑不出 $a_l$ 那么直接令 $L_r=l+1$，$r$ 就没有用了，因为对于后面的 $l$，由于我们无法凑出 $b_l$，因此 $\forall l'\in[1,l],w(l',r)=1$。

可以动态维护一个线性基栈，依次是 $(l,r_1],(r_1,r_2],\dots$，如果 $b_l=0$，就直接将区间 $(l-1,l]$ 压栈，否则看 $(l,r_1]$ 能否凑出 $a_l$，能就不管，不能就 $L_{r_1}\leftarrow l+1$，并将 $(l,r_1]$ 并到 $(r_1,r_2]$，继续判断。

这里线性基合并是均摊 $O(nw)$ 的，因为每一个数字只会在每一位插入失败一次。

总时间复杂度 $O(nw+(n+q)\log n)$，空间 $O(nw)$。

不强制在线的原因是可持久化空间花费太大，以至于无法体现时间优势。

因为时空限制都是两倍，所以场上也有人写线段树通过，不卡同复杂度的解法。

可以使用前缀线性基做到一样的复杂度，不需要线性基合并。