题解七影蝶

fjy666 · 2024-12-17 11:44:49 · 题解

Subtask 1,2,3

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

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

考虑用更高妙的方法维护出 \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）

这一部分参考代码。

观察线段树，第 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)。

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

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

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

~~通过了~~杀了。

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