本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-04 15:31:09

题意

维护序列 $a$，需要支持区间变为异或差分，单点查询，最后输出整个序列。$n\le 2.5\times 10^5,q\le 10^5,a_i<2^{30}$。

题解

先考虑 D 性质，即 $l=1,r=n$ 的情况。此时若进行了 $x$ 次操作，则目前 $a'i=\bigoplus{j\subseteq x}a_{i-j}$，其中 $j\subseteq x$ 表示二进制下 $j$ 为 $x$ 的子集。证明可考虑 $x$ 行的网格图，其所有格中均存在左上到右下的对角线，要求只能向下或右下走。则 $a_{i-j}$ 对 $a'i$ 的贡献次数即为 $(0,i-j)$ 到 $(x,i)$ 的路径条数 ${x}\choose{j}$，根据卢卡斯定理可得当且仅当 $j\subseteq x$ 时有 ${x\choose j}\equiv 1\pmod 2$，$a{i-j}$ 对最终 $a'_i$ 有贡献。

然而 $x$ 较大时无法直接枚举子集，考虑定期重构，每当 $x=B=2^k$ 时更新整个序列并将 $x$ 清空。注意到此时子集只有 $0$ 和 $2^k$，可以 $O(n)$ 更新，复杂度为 $O(\frac{nq}B)$。这样查询时 $x$ 不会超过 $2^k$，直接枚举子集即可，复杂度为 $O(qB)$。取 $\sqrt n$ 附近的 $2^k$ 作为 $B$，得到总复杂度为 $O(q\sqrt n)$。

变为区间修改时，仍对每 $B$ 个修改分一块，回答其内部的询问，同时更新出整个序列在这 $B$ 次修改后的值。注意到由于修改次数不超过 $B$，此时 $a'_i$ 的值只受 $[i-B,i]$ 内 $a$ 值的影响。因此我们再对序列每 $B$ 个元素分一块，则某块内元素的值只受该块和前一个块影响。因此可以先枚举操作块，再枚举序列中每个块依次处理，此时只需要考虑序列中的两个块。

具体地，处理块 $i$ 时拿出块 $i,i-1$，若修改完全包含两个块则只累加 $x$ 标记；若修改只包含两块的一部分，则要清空 $x$ 标记并重构两个块，再进行区间暴力修改。对于某个在块 $i$ 内的询问，可将标记清空再查单点值，或直接枚举 $x$ 的子集求答案。这里清空标记不能暴力枚举所有 $x$ 的子集，而是要进行类似高维前缀和的操作，即枚举每个 $x$ 是 $1$ 的二进制位 $2^k$，并倒序更新所有 $a_i\leftarrow a_{i}\oplus a_{i-2^k}$，容易发现这样操作的结果与暴力枚举子集相同，复杂度 $O(B\log B)$。

现在计算复杂度。有 $O(\frac nB)$ 个序列块，区间修改影响至多四个块，处理时标记清空复杂度 $O(qB\log B)$，暴力更新复杂度 $O(qB)$。每次查询时若清空标记有 $O(qB\log B)$ 的复杂度，若暴力枚举子集有 $O(qB)$ 的复杂度。另外有 $O(\frac qB)$ 个操作块，每个操作块处理完后需下放所有序列块的标记，复杂度 $O(\frac{nq}{B^2}B\log B)=O(\frac {nq\log B}B)$。综上所述总复杂度为 $O(qB\log B+\frac{nq\log B}B)$，取 $B=\sqrt n$ 可得 $O(q\sqrt n\log n)$。这里给出了特殊性质和两种答案统计方式的代码，其中枚举子集的常数较小。