CTS 2022 Day 1 A. 普罗霍洛夫卡

Statement

给定一个序列 $a$，以及 $m$ 次询问。每次询问给定一个区间，查询其所有子区间的权值异或和，一个区间 $[l,r]$ 的权值定义为 $a[l,r]$ 中数的种类数。

$1\leq n,m\leq 4\times 10^5.$

TL: 10s

Solution

把每一种数对区间的贡献放在其第一次出现上，因此每个 $i$ 对所有 $pre_i

我们画到 $n\times n$ 矩形上就可以发现影响是一个 3-side 矩形加 $1$，询问是查询子矩形异或和，按照 $r$ 从小到大扫描线，需要支持区间加一，区间历史异或和。

从操作的组合意义上讲我们可以发现对于某一行，$l$ 从大到小的权值不降，而且相邻两项差不超过 $1$。

这个问题看起来就不好合并信息，因此我们认定只能分块，设块长为 $B_1$。

我们坚定这样一个策略：遇到散块就重构块内信息（发生 $\mathcal{O}(m)$ 次），整块我们期望直接调用预处理信息来更新整块历史异或和。

那么我们需要对于每个整块维护对于每个块与每个 $x$ 维护出 $f_x=\bigoplus\limits_{i=0}^{B_1-1}(x+a_i)$，这样当时间戳加一时只需要将整块历史异或和异或上 $x$ 取当前标记时的结果。

为了确保信息量的规模是可以接受的，我们进行定期重构，当加法标记等于 $B_2=2^{\lfloor\frac{\log_2 n}{2}\rfloor}$ 时我们也重构块内信息，这样的重构也只会发生 $\mathcal{O}(\frac{n^2}{B_1B_2})$ 次，同时使得 $x\in[0,B_2)$。

然后再考虑如何重构，由前面的性质（似乎其实不需要单调性）可知一个块内极差小于 $B_1$，然后你有一些标记时刻对单点历史和产生了贡献，因此翻转 $a,x$ 的地位依然相当于维护 $x\in[0,B_1)$ 的 $g_x=\bigoplus\limits_{i=0}^{t-1}(x+a_i)$，其中 $t\leq B_2$。

所以我们令 $B=B_1=B_2$ 就好，接下来只需要解决 $\mathcal{O}(B)$ 进行对于长度不超过 $B$ 的序列 $a_i$ 以及所有 $x\in[0,B)$ 的 $x$ 维护出 $\bigoplus_i(x+a_i)$。

记 $k=\lfloor\frac{\log_2 n}{2}\rfloor$。

对于不低于 $k$ 位的部分，每个 $a_i$ 只有至多两种贡献，且一定是 $x$ 某个前缀全都是第一种，其余全都是第二种，因此容易差分维护。

对于剩下 $k$ 位，我们维护一个加法器即可，容易做到 $\mathcal{O}(\sum\limits_{i=0}^{k-1} 2^i)=\mathcal{O}(2^k)=\mathcal{O}(B)$。

每个区间独立，直接离线下来逐块来做空间就是线性了。