自动搬运

查看原文

来自洛谷，原作者为

	fjy666 请将我幻葬

搬运于2025-08-24 23:09:34，当前版本为作者最后更新于2024-12-17 11:44:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Subtask 1,2,3

$V$ 较小，因此可以枚举 $1\le i\le V$，计算出 $\texttt{ans}_i=\sum_{j=1}^n \operatorname{popcount}(a_j+i)$，最后询问做 RMQ。

$\texttt{ans}_i$ 可以通过将所有数插入 01 Trie，然后每次对 01 Trie 做全局 $+1$ 维护答案得到。时间复杂度为 $\mathcal{O}(V\log V+q\log V)$

Subtask 5

可以通过修改 Make Equals 的做法过这一档分。

Subtask 4,6

考虑用更高妙的方法维护出 $\texttt{ans}_i$。

拆位，$a_i+j$ 的第 $k$ 位为 $1$ 可以转化为 $j$ 的后 $k$ 位在一个值域区间内，因此假如只考虑第 $k$ 位的话，$\texttt{ans}$ 数组可以被 $n$ 次区间加 $1$ 维护出来。

假设你已经维护出了第 $k$ 位及以下的 $\texttt{ans}_i(0\le i<2^k)$，可以发现第 $k+1$ 位的线段树根节点 $[0, 2^{k+1})$ 的两个儿子 $[0, 2^k)$ 和 $[2^k, 2^{k+1})$ 关于第 $k$ 位及以下的信息都是完全一致的。

因此我们对线段树进行可持久化，然后每次 $k\gets k+1$ 时新建根节点，然后把根节点的两个儿子都指定为前一层的根结点，同时将根节点维护的值域扩大两倍即可。

（我称呼它为值域倍增线段树）

空间，在新建节点的时候需要判一下这个节点是不是这一层已经新建过的，如果是的话就不要新开节点了。

时空复杂度均为 $\mathcal{O}(n\log^2V)$，期望得分 $55\sim 70$。（Sub 5 的线段树卡了常，这不是出题人本意，被卡的老师们对不起/wq）

这一部分参考代码。

Subtask 7,8 (improved by Zhoukangyang)

观察线段树，第 $k$ 层的 $\mathcal{O}(n)$ 次区间操作会把线段树分成 $\mathcal{O}(n)$ 段，每段所受到的区间加操作是完全相同的。

这些“段”在 $k$ 层的操作相同，在 $>k+1$ 层受到的操作必定也是相同的，因此考虑每次做完区间加后把受到操作相同的值合并起来。

合并后会有 $\log V$ 层，每层有 $\mathcal{O}(n)$ 段。每一段需要储存：区间 $\max$，以及被打的标记的总和。

查询类似线段树，中间整段做区间 $\max$，左右两端往下递归，递归需要带上标记，类似标记永久化。

使用双指针与线性 RMQ 优化可以做到 $\mathcal{O}((n+q)\log V)$，不加这些是 $\mathcal{O}(n\log V+q\log^2 V)$。

Extra

存在 Meet in the middle 做法。大概是后 $26$ 位预处理，然后对于询问枚举前 $6$ 位从而平衡复杂度。

这个是出题人没想到的，出题人在比赛时看到这个做法后上巴吓得掉下去了。

EuphoricStar 在赛时最后 1min 用这个做法绝杀了这个题。Orz

通过了杀了。

致：鹰原羽依里先生
我愿越过七片大洋，与君相会。
满怀着我的爱意。
胡子猫海盗团 · 久岛鸥