题解 practiceZ

· · 题解

下面认为 m=\Theta(n)。

对 b 序列分块，块 x 内维护 \sum_{b_{id}\in x} \sum_{i=1}^{b_{id}} a_i。

考虑 a 序列的修改。区间推平不好做，考虑用颜色段均摊方法（ODT）转为区间加。那么要修改 b 的每个块的值。

修改 a_x 会对块内所有 b_i\ge x 的 b_i 做出贡献。

设值域数组 t（t_i 表示 b=i 的次数）。设区间加数为 v，则贡献为 \sum_{i=l}^r \sum_{j=i}^n t_j \times v=v\sum_{i=l}^r \sum_{j=i}^n t_j。用一些数据结构维护即可。

查询的时候，整块直接查，对于散块查询，需要对 a 维护一个 O(\sqrt n) 区间加，O(1) 前缀求和的分块。

考虑 b 序列的修改。对于整块修改可以直接打标记。散块操作的难点在于维护值域上的后缀和的区间求和。每个块维护一个 ODT，这样就可以插入/删除颜色了。现在要维护一个数据结构，支持：

分成两类计算。 * $j\le x$。对于这类数，$t_j$ 出现了 $j$ 次。那么这部分的贡献是 $\sum_{j=1}^x t_j \times j$。 * $j>x$。这类数每个数都出现了 $x$ 次。贡献为 $x\sum_{j=x+1}^n t_j$。 两类都可以用分块处理。 注意修改 $b$ 序列的时候同时维护每块的值。 为了做到线性空间，我们需要离线逐块处理。 在逐块处理的时候，要用一些手段让复杂度不退化到 $O(n^2)$。大概就是把 $1,2$ 操作的贡献分别算，以规避掉逐块处理时每块都要对 $a$ 数组维护分块的过程。 注意细节。 时间 $O(n\sqrt n)$，空间线性。 非常神奇的，每一处都恰好根号平衡。 卡常的话自己摸索一下？很快乐的。 btw，这个卡常还是叉姐以前教我的/流泪