自动搬运

查看原文

来自洛谷，原作者为

	zyc070419 **

搬运于2025-08-24 22:53:52，当前版本为作者最后更新于2024-01-11 11:55:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

前置知识

• 分块
• 组合
• Kummer 定理
• 高维前缀和

题解

各部分的代码都放到最后了……

Subtask #1

$\mathcal{O}(nq)$ 模拟即可。

Subtask #2

由于 $\forall i\ge 2,a_i=0$，所以说经过若干次操作之后得到的新数列 $\{a_n'\}$ 一定满足：$a_i'=0$ 或 $a_i'=a_1$，所以设 $b_i=[a_i'=a_1]$。然后就可以 $\texttt{bitset}$ 优化，复杂度 $\mathcal{O}(\dfrac{nq}{w})$。

Subtask #3

$\texttt{bitset}$ 优化即可，复杂度 $\mathcal{O}(\dfrac{nq}{w})$。

Subtask #4

$D$ 性质的本质相当于对整个数列做 $k$ 次差分。

引理一：

对于整个数列做 $k$ 次差分之后的数列 $\{a_n'\}$ 满足：

$$a_i=\bigoplus_{j=1}^{i}a_j\left[\binom{k}{i-j}\equiv 1\pmod 2\right] $$

证明方法与数列的 $k$ 次加法差分结果证明类似，有两种理解方法：

第一种较为代数的理解，因为位运算每一位独立，所以可以每一位单独考虑，下文设 $a_i\in \{0,1\}$。设幂级数 $F(x)=\sum_{i\ge 0}a_i x^i$，而异或相当于不进位加法，所以先当成加法来考虑，则进行一次差分相当于将 $F(x)$ 乘 $(1-x)$，那么 $k$ 次差分就有：

$$\begin{aligned} F_k(x)&=F(x)\times (1-x)^k\\ &=\sum_{i\ge 0}a_x\times x^i\sum_{j\ge 0}(-1)^j\binom{k}{j}x^j &=\sum_{i\ge 0}x^i\sum_{p+q=i}a_p\times (-1)^q\times \binom{k}{q} \end{aligned} $$

所以 $[x^n]F_k(x)=\sum_{i}a_i\times (-1)^{n-i}\times \binom{k}{n-i}$。那么异或差分的系数就是：

$$(\sum_{i}a_i\times (-1)^{n-i}\times \binom{k}{n-i})\bmod 2=\bigoplus_i a_i\Bigg[\binom{k}{i-j}\equiv 1\pmod 2\Bigg] $$

第二种理解方式比较组合：考虑 $a_i$ 在一次差分之后会向哪里贡献对：$a_i'$ 和 $a_{i+1}'$ 分别贡献一次，所以说 $a_j$ 对 $a_i'$ 的贡献次数就是：有一个点最开始在 $j$，操作 $k$ 次，每次选择向右走一个单位或者原地不动，$k$ 次之后到达 $i$ 的方案数，也就是 $\binom{k}{i-j}$。方案数为奇数就让 $a_i'$ 异或 $a_j$，否则不修改。

又因为当且仅当 $a_j\not=0$ 时才有可能对 $a_i'$ 的值有影响，所以说可以只枚举 $a_j$ 不为 $0$ 的位置计算，复杂度 $\mathcal{O}(c(n+q))$。

Subtask #5

只用知道最后一次操作，所以说可以卷积，可以选择进行 DP。

首先由上可知，$a_j$ 能对 $a_i$ 产生贡献当且仅当 $\binom{k}{i-j}$ 为奇数，也就是不含 $2$ 的次幂，那么可以考虑 Kummer 定理：$\binom{k}{i-j}$ 为奇数当且仅当 $k\ \operatorname{and}\ (i-j)=(i-j)$，其中 $\operatorname{and}$ 是按位与运算。那么设 $dp_{i,p}$ 表示所有满足 $i-j$ 在二进制下的最高位不超过第 $p$ 位并且满足 $k\ \operatorname{and}\ (i-j)=(i-j)$ 的 $a_j$ 的异或和。那么有转移：

$$\left\{ \begin{matrix} dp_{i,p}&=&dp_{i,p-1} && k_p=0\\\\ dp_{i,p}&=&dp_{i,p-1}\oplus dp_{i-2^p,p-1} && k_p=1 \end{matrix} \right. $$

$k_p$ 表示 $k$ 在二进制下的第 $p$ 位。

复杂度 $\mathcal{O}(n\log n+q)$。

Subtask #6

因为多次单点询问，每一次询问的之后差分的次数不一样，并且不好递推，所以自然想到分块。

为了与我的代码表现一致，下文中记 $K$ 表示 $k$ 取反后的结果，这样条件就变成了 $K\ \operatorname{and}\ (i-j)=0$。

规定 $\operatorname{lowbit}(x),\operatorname{highbit}(x)$ 分别表示 $x$ 在二进制下的最低位，最高位。

因为可以发现我们异或的是一段一段区间，异或的每一段的区间长度为 $2^{\operatorname{lowbit}(K)}$，任意两个需要异或的区间之间的距离最短是 $2^{\operatorname{logbit}(K)+1}$。所以如果 $\operatorname{lowbit}(K)$ 很大就好了，所以想到了根号分治，或者说值域分块。先设置一个阈值 $B$。

$dp_{i,j}$ 表示当 $K=j$ 时 $a_i'$ 的值，其中 $j< 2^B$。记 $sum_{l,r}=\bigoplus_{i=1+1}^ra_i$。记 $l(x)=2^{\operatorname{lowbit}(x)},h(x)=2^{\operatorname{highbit}(x)}$

为了让转移式子情况没有那么多，下面规定 $\forall i \le 0，a_i=dp_{i,j}=0$。然后就有转移：

$$\left\{ \begin{matrix} dp_{i,j} &=& dp_{i-2j,j}\oplus sum_{i-j,i}&& \operatorname{lowbit}(j)=\operatorname{highbit}(j)\\\\ dp_{i,j} &=& dp_{i,j-h(j)}\oplus dp_{i-h(j),j-h(j)}\oplus dp_{i-2h(j),j}&& otherwise. \end{matrix} \right. $$

由于 $B$ 位以下的要求已经处理完了，但是无法保证 $B$ 位及以上是否满足要求，所以说 $a_i'$ 最终的答案是：

下面记 $y=(K\ \operatorname{and}\ (2^B-1)),x=K-y$。

$$\bigoplus_{j\ge 0}(dp_{i-j\times 2^B,y}\oplus dp_{i-(j+1)\times 2^B,y})\big[(j\times 2^B)\ \operatorname{and}\ x=0\big] $$

预处理 DP 复杂度 $\mathcal{O}(n\times 2^B)$，询问复杂度 $\mathcal{O}(\dfrac{nq}{2^B})$。取 $B=8$ 时较为优秀。总复杂度大致可以看作 $\mathcal{O}(n\sqrt{q})$。

Subtask #7, 8

我不是很清楚 Subtask #7 具体有什么算法，或许有什么必须依赖离线的方法？

因为上面的算法只能处理全局差分，但现在是区间差分，没法搞，所以可以分块。

对序列分块，整块打整体差分 $\text{tag}$，散块暴力。然后整道题就解决了。

可以发现如果只这样搞得话显然很难维护，因为假设我们给第 $i$ 个整块 $[l,r]$ 打了一次 $\text{tag}$，那么这次操作带来的影响还跟打 $\text{tag}$ 之前 $a_{l-1}$ 的真实值有关，所以我们需要把每一次打 $\text{tag}$ 之前的 $a_{l-1}$ 的真实值也维护。

所以说可以尝试先把每次修改前 $a_{l-1}$ 的值存下来。

现在先假设我们已经把所有操作前 $a_{l-1}$ 的值存了下来，整块 $[l,r]$ 到现在一共进行了 $m$ 次操作，第 $i$ 次操作前 $a_{l-1}$ 的真实值是 $v_i$。那么现在如何快速下放 $\text{tag}$ 进行还原呢？

由于对于 $i\in[l,r]$，有：

$$a_{i}'=(\bigoplus_{j=l}^{i}\binom{m}{i-j}a_j)\oplus (\bigoplus_{j=1}^{m}b_{i,j}\times v_j) $$

其中 $b_{i,j}$ 是 $v_j$ 对 $a_i$ 的贡献系数，$b_{i,j}\in \{0,1\}$。

左半部分是可以按照 Subtask #5 的方法 DP 的（这部分的贡献在下文称作 段内贡献），而右半部分（这部分贡献下文称作 特殊贡献）首先要求出系数：

考虑组合意义（其实代数肯定也能推，但比较麻烦）：

$v_i$ 在第 $i$ 个时刻第一次到达 $l$ 这个位置，然后还剩下 $m-i$ 个时刻可以移动，并且剩下的 $m-i$ 个时刻每次可以选择原地不动或者向右一步，贡献系数就是路径方案数，即：

$$b_{i,j}=\binom{m-j}{i-l}\bmod 2$$

然后再用一次 Kummer 定理，当且仅当 $(m-j)\ \operatorname{and}\ (i-l)=(i-l)$ 时才有贡献。那么如果 $m$ 是固定的，就能先设数组 $V_i=v_{m-i}$，然后对 $\{V_0,\cdots ,V_{m-1}\}$ 做高维后缀异或和得到 $V'$，那么 $v$ 数组对 $a_i$ 的贡献就是 $V_{i-l}'$。综上即：

$$a_{i}'=(\bigoplus_{j=l}^{i}\binom{m}{i-j}a_j)\oplus V_{i-l}' $$

那么如何维护 $v$ 数组呢？要求出 $v_i$ 就需要求出 $a_{l-1}$ 的值，但又不能把 $a_{l-1}$ 所在的成块还原，不然复杂度又变成 $\mathcal{O}(n^2)$ 的。所以说要支持动态单点算出 $a_{l-1}$，更一般性的说，要快速算出每一段（除了最后一段）末尾一个元素的真实值。

求解方法跟上面说的一样分成两块：

假设第 $i$ 个整块的区间为 $[L_i,R_i]$。下文以第 $i$ 个整块为例说明 $a_{R_i}$ 如何求。

对于段内贡献，可以求出新的数组 $A_j=a_{R_i-j},j\in [0,R_i-L_i]$，然后对 $A$ 作高维前缀和得到 $A'$ 数组，那么如果整块差分了 $t$ 次，段内贡献就是 $A'_m$。而整块打 $\text{tag}$ 是部分影响块内的值的，也就是说 $A'$ 数组在整块操作中是不会改变的，如果散块暴力的时候会改变，所以求解是可以接受的。

对于特殊贡献，因为 $m$ 会变，所以 $V$ 在不断的改变，高维后缀和也在不断的改变，那就没法维护了，所以做不了了。

$m$ 虽然在变，但是 $R_i-L_i$ 是不会变的，所以说要从这个地方为突破口。

如果 $x\ \operatorname{and}\ (2^t-1)=(2^t-1)$，其中 $t$ 为一个常量，那么说明 $x\equiv -1 \pmod {2^t}$。

这个很重要，把位运算变成了我们熟悉的运算。所以说，如果设 $R_i-L_i=2^t-1$ 特殊贡献就相当于：

$$\bigoplus_{j=1}^{m}v_j\big[m-j\equiv -1 \pmod {2^t} \big]=\bigoplus_{j=1}^{m}v_j\big[j\equiv m+1 \pmod {2^t} \big] $$

所以记 $val_{j}=\bigoplus_{p=1}^{m}v_p\big[p\equiv j \pmod {2^t} \big]$，然后当操作次数为 $m$ 次时特殊贡献就是 $val_{(m+1)\bmod 2^{t}}$。

综上所述就完成了对于 $a_{R_i}$ 的动态求解，设块长 $B=2^t$，复杂度为 $\mathcal{O}(qB\log B+\dfrac{nq}{B})$，当 $t=8$ 时最优。

代码在这里，代码中的 subtask1，subtask2,subtask3,subtask4 分别对应原题中的 Subtask #1，Subtask #2~3，Subtask #4~6，Subtask #7～8。