P10009 [集训队互测 2022] 线段树

我们先考虑全局操作的影响。

我们对每个位置考虑前面位置对它的贡献，根据差分序列的性质，当你做了 \(k\) 次异或差分，可以看作每次每个位置贡献给下一行的这一个位置和右侧一个位置，即 \(c_{i,j} \to c_{i+1,j},c_{i+1,j+1}\) ，这个东西显然和杨辉三角等价，贡献方式可以视作每次向下一行两个位置走一步，所以你走右侧那个格子的次数就是你和目标位置的横坐标差。

这个东西显然可以组合数解决，也就是说，\(a_j \to a_i\) 的贡献次数是 \(C_k^{i-j}\) 次，由于是异或，所以实际贡献系数需要对 2 取模，而组合数对 2 取模，考虑套用 Lucas 定理，即：组合数对固定模数 \(p\) 取模的值是其两个系数拆成 \(p\) 进制后每一位依次计算组合数并且求积的值。当 \(p = 2\) 的时候，答案为 1 当且仅当对于任何一位，不存在这一位上 \(k\) 为 0 且 \(i - j\) 为 1，即，\((i - j) \in k\)，\(i - j\) 在二进制下是 \(k\) 的子集。

于是通过这个关键结论，我们知道，我们想求的值是这样的：

我们便可以考虑通过 dp 得出每个位置的实际值，我们试着从高维前缀和的 dp 理解出发去设计，设计 \(f_{d,i}\) 表示当我们只考虑 \(i - j < 2^d\) 的 \(j\) 的时候，\(s_i\) 的值，那么我们考虑倍增式地转移，即我们想把 \(i - j \geq 2^{d}\) 且 \(i - j < 2^{d+1}\) 的 \(j\) 的贡献加入，当然，这必须满足 \(k\) 在 \(d\) 这一位为 \(1\) ，否则就不满足子集的条件。随后发现，这个贡献是 \(i - j < 2^d\) 的距离为 \(2^d\) 的平移，即等式左右同减 \(2^d\)， \(i - (j + 2^d) < 2^d\) 的贡献。拆开括号，可以发现其实这就是 \((i - 2^d) - j < 2^d\) ，即 \(f_{d,i - 2^d}\) 的贡献。因此，我们得到了转移方程 \(f_{d+1,i} = f_{d,i} \oplus f_{d,i-2^d}\)。

到此为止，我们解决了全局操作的部分。

但此题的结构非常神秘，要支持以上所有操作，是不太可能用具有性质的数据结构完成的，考虑只能进行分块了，那么我们的根本思想就是对散块暴力修改，和通过打标记的方式，更新整块的信息，同时，我们在散块修改前，还需要对整个块下传标记，重构，以得到正确的信息以供暴力。

我们先来考虑，当一个块是整个数组第一个块，即前面不存在新的元素可以对这个块造成影响，而仅有这个块内对自身造成影响的情况：发现这和全局的情况完全一致，只需要对这个块做全局操作的部分即可，我们约定一个块开头的元素为 \(s_l\) ，末尾的元素为 \(s_r\)。

但是，对于其余的块，前面一个块的元素，甚至更前面的块的元素，都有可能会影响到这个块，那我们先考虑前一个块的元素，前一个块的元素唯一能造成影响的，便是前一个块的末尾。我们试图在打标记的时候储存前一个块的末尾元素的真实值，以供我们通过某种方式计算这个值对我们块内每个位置的贡献，设我们进行了 \(k\) 次操作，而我们储存的前一个块末的值为 \(g_0,g_1,\cdots,g_{k-1}\)。如果我们知道了这些值，由于倒数第 \(j\) 个操作时，\(g_{k-j}\) 仅会影响我们这一块的 \(s_l\)，那我们只需要考虑在后面 \(j\) 次操作，\(s_l\) 对块内元素的影响，根据已知结论，\(s_l\) 影响 \(s_i\) 的系数为 \([i - l \in k]\)，这意味着，我们每个 \(i - l\) 会被其所有为其二进制超集的 \(k\) 的 \(g_k\) 影响，那我们只需要通过一次 FWT 求出超集异或和，从而更新块内答案。

那么，我们如何在打标记的时候知道上一个块的 \(s_r\) 的真实值呢？我们意识到，如果块内的标记次数过多，以至于标记次数超过了块长，不仅仅是这一个块，甚至上一个块，都会影响这一个块末尾的值，那我们可能会产生“连锁反应”，导致大量的互相影响，这并不是我们想看到的。考虑在块内标记数超过块长时候重构整个块的全部信息，这样的情况便不会出现。

因此，在这样的条件下，一个块的 \(s_r\) 只会被块内元素影响，并且我们对于每个块都只需要知道这一个值。那么考虑直接处理出每个块的 \(s_r\) 在操作 \(k\) 次（其中 \(k\) 不超过块长）后的真实值 \(w_k\)。我们通过以上关于系数的结论可知，块内距离 \(r\) 为 \(i\) 的元素，在操作 \(k\) 次后对 \(s_r\) 的贡献系数为 \([i \in k]\)，即，每个 \(i\) 会对其超集贡献。因此，我们可以通过 FWT 求出子集和，来得到每个 \(w_k\) 。

我们设块长为 \(B\)，我们无论是做 dp，还是进行 FWT，复杂度都是 \(O(B \log B)\)。而我们标记总数是 \(O(\frac{nq}{B})\)，当标记个数达到 \(B\) 次，我们便会重构，因此重构次数是 \(O(\frac{nq}{B^2})\) 的，因此总复杂度 \(O((q + \frac{nq}{B^2})B \log B)\)，当 \(B = \sqrt n\) 时，总复杂度为 \(O(q \sqrt n \log B)\) 。