题解：P13834 【MX-X18-T6】「FAOI-R6」Voices of the Chord

xxxxxzy · 2025-08-24 21:44:48 · 题解

下面默认 n,m,k 同阶。

首先考虑一个弱化版问题，保证 l=r，尽管完全没有关系。

这个是很好做的，根号分治一下集合大小，然后离线随便整下拿个分块平衡一下就轻松 O(n \sqrt n)。

再考虑一个简单的问题，保证 b_i=i，好像也没啥关系，这个也是简单的可以做到根号，简单说一下，把集合给拆开，然后进行分块，维护 f_{i,x} 代表块 x 的修改对前缀 i 的贡献，时空都是根号。

上面的子问题给我们一个思路，对序列进行分块，维护一些预处理信息。

首先考虑对 b 进行分块，为了防止混淆，记 B_i 代表 b 数组的第 i 个块，另外记 T_i 代表包含 i 下标的集合。

按照上面的思路，维护出 f_{i,j} 代表，B_i 对 a 前缀 j 的贡献。

但是这样会剩下散块信息难以维护，我们考虑对散块信息再次加以处理。

进行转化，转化为下面的子问题：

感觉也是难以维护的，发现其实第一个要求 O(1) 完成的操作在原序列上是连续的，而没有较好利用这个连续性。

考虑对 a 也进行分块，记 A_i 为 a 的第 i 个块。

我们只需要处理两类贡献。

第二类贡献仍然不太好做，因为 a 的散块可能总大小很大。

继续利用一下 \sum |T| = \sum |S| 的性质，对 a 进行以 |T_i| 为权的带权分块，让块的权重 \le \sqrt S，这样散块修改就是对的。

记 V = \sum S_i，时间 O(V \sqrt n + (n + q) \sqrt V)，空间 O(n \sqrt V)，时间瓶颈在预处理上，代码实现比较简单，2 KB 左右。