自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:34:53，当前版本为作者最后更新于2021-09-02 22:00:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

下面认为 $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，这样就可以插入/删除颜色了。现在要维护一个数据结构，支持：

$O(\sqrt n)$ 单点加，$O(1)$ 求 $\sum_{i=1}^x \sum_{j=i}^n t_j$。

分成两类计算。

• $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，这个卡常还是叉姐以前教我的/流泪