本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-28 15:22:26

:::::info[题目基本信息] 考察：分块，Lucas 定理，动态规划 DP（NOI/NOI+/CTSC）。
题目简介：
给定 $\{a_n\}$，$q+n$ 次操作，操作分为两类：

1. 给定 $l,r$，进行操作 $\forall i\in(l,r]$，同时令 $a_i\leftarrow a_i\oplus a_{i-1}$。
2. 给定 $pos$，求 $a_{pos}$ 的值。

其中操作满足条件：$\forall i\in[1,n]$，第 $q+i$ 次操作都是第二种操作，且 $pos=i$。
数据范围：

• $1\le n\le 2.5\times 10^5$。
• $1\le q\le 10^5$。
• $\forall i\in[1,n],0\le a_i<2^{30}$。
• 对于第一种操作，$1\le l\le r\le n$。
• 对于第二种操作，$1\le pos\le n$。

时间限制：3s。
空间限制：512MB。
::::: :::::info[闲话] KSCD 太巨了！
本题解有借鉴其题解相关内容。
::::: 通过观察数据范围，是 $10^5$ 量级的，然后开了 3s，猜测是根号复杂度带个 $\log$，同时莫队没有什么好突破，所以开始想分块。
同时如果对序列分块的话可能会有多次第一种操作导致影响力超过 $\Theta(1)$ 个块，所以考虑同时对序列和操作分块。
根据上述，我们设阈值为 $B$，对序列每 $B$ 个分一块，当第一次操作数达到 $B$ 时分一块，这样保证了影响力只会在相邻两个块间产生，那么我们做的时候就会简单一点。
现在我们考虑如何快速计算它们多次异或后的值，容易发现若进行了 $d$ 次操作，那么 $a'j$（多次操作前的 $a_j$）会贡献到 $a_i$ 这个地方 $\dbinom{d}{i-j}$ 次，现在需要判断这个值的奇偶性。
:::::success[引理]{open} 当且仅当二进制下 $y\subseteq x$ 时，$\dbinom{x}{y}$ 为奇数。
::::: :::::success[证明] 由 Lucas 定理：
$$\binom{x}{y}\equiv\binom{\lfloor\frac{x}{p}\rfloor}{\lfloor\frac{y}{p}\rfloor}\binom{x\bmod p}{y\bmod p}\pmod p$$ 其中 $p$ 是质数。
当 $p=2$ 时，我们得到：
$$\binom{x}{y}\equiv\prod{i=0}\binom{x_i}{y_i}\pmod 2$$ 其中 $x_i,y_i$ 分别代表 $x$ 和 $y$ 在二进制下第 $i$ 位的值。
注意到 $\dbinom{0}{0}=\dbinom{1}{0}=\dbinom{1}{1}=1$，只有 $\dbinom{0}{1}=0$，所以最终容易得到原引理。
证毕。
::::: 所以通过上面的引理我们得到：
$$a_i=\bigoplus_{i-j\subseteq d}a'_j$$ 这个式子可以使用 SOS DP 进行计算。
那么计算后有什么用呢？
具体地，我们对于相邻两个块，当这个操作是第一种操作且操作完全覆盖这两个块的时候我们令 $d\leftarrow d+1$，否则我们通过 SOS DP 直接清空标记然后对块内的数暴力进行操作即可。对于查询我们可以直接枚举子集计算。
这样复杂度是否正确？
对于每个第一种操作，容易发现被暴力计算的块最多只有 $4$ 个，所以暴力计算这部分的复杂度是 $\Theta(qB)$，同时在清空标记时会有 $\Theta(qB\log B)$ 的复杂度，查询时枚举子集会有 $\Theta(qB)$ 的复杂度，同时每个操作块结束时需要下放标记，会有 $\Theta(\dfrac{nq\log B}{B})$，所以总复杂度是 $\Theta(\dfrac{nq\log B}{B}+qB\log B)$，取 $B=\sqrt n$ 可得到 $\Theta(q\sqrt n\log n)$ 的复杂度。
时间复杂度为 $\Theta(q\sqrt n\log n)$，空间复杂度为 $\Theta(n+q)$。

code