异或线性基解决一类博弈问题||P9580 题解（2023 激励计划评分 10）

· · 题解

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

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

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

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

找子集异或起来等于给定数字就是异或线性基模板，于是我们能够成功解决一次博弈的胜负了，这样时间复杂度为 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)。

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

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

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