P10009 题解
zyc_lIIll
·
·
题解
P10009 [集训队互测 2022] 线段树 题解
前置知识
题解
各部分的代码都放到最后了……
Subtask #1
### 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 的（这部分的贡献在下文称作 段内贡献），而右半部分（这部分贡献下文称作 特殊贡献）首先要求出系数：
考虑组合意义（其实代数肯定也能推，但比较麻烦）：
$$
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$ 时最优。
代码在[这里](https://www.luogu.com.cn/paste/2mrrz1th)，代码中的 `subtask1，subtask2,subtask3,subtask4` 分别对应原题中的 Subtask #1，Subtask #2~3，Subtask #4~6，Subtask #7～8。