自动搬运

查看原文

来自洛谷，原作者为

	WrongAnswer_90 别爆零了

搬运于2025-08-24 23:11:26，当前版本为作者最后更新于2025-03-26 19:53:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为时限太搞笑所以暴力分块可以过。但是怎么没人说复杂度对的做法啊。

操作是维护 $b$ 序列，支持前缀加，查询前缀内 $a_i$ 大于等于 $x$ 的位置 $b_i$ 的和。

操作强于行加列求和，显然得根号。暴力的单根号很简单，看其他题解吧。考虑 $nmz\leq 10^{16}$ 怎么用，我们希望能编一个 $\mathcal O(\sqrt{nmz})$ 的东西出来。

操作分块，每 $B$ 个修改操作分一块。这样一共会分成 $m/B$ 块。处理到第 $i$ 块的时候，需要计算 $[1,i-1]$ 的块对这之中的询问的贡献，以及第 $i$ 块内部的修改对询问的贡献。

$[1,i-1]$ 块的贡献

计算出 $f_j$ 表示处理了 $[1,i-1]$ 的块内的所有修改，此时 $j$ 的权值，这部分复杂度是 $\mathcal O(nm/B)$。查询就是一个二维数点。

总的修改次数是 $\mathcal O(nm/B)$ 级别的，而查询数只有 $z$。考虑平衡一下复杂度。

因为 $z$ 也是 $10^6$，常规分块复杂度还是有点高。所以可以分三层的块：设 $T=100$，每 $T$ 个位置分一个小块，这样一共有 $10^4$ 个小块。然后每 $T$ 个小块建立一个大块。维护每个点的值，小块内部的和，和大块内部的和，修改是 $\mathcal O(1)$，查询 $\mathcal O(T)$。

块内的贡献

一个修改操作 $(p_i,w_i)$ 对一个查询操作 $(q_j,d_j)$ 的贡献是 $[1,\min(p_i,q_j)]$ 内，$a$ 大于等于 $d_j$ 的点数 $\times w_i$，也就是 $zB$ 次数点，总点数是 $n$。这部分也是和上面一样的三层分块，只不过维护的是块内前缀和，大块内的小块前缀和，大块前缀和。修改 $\mathcal O(T)$，查询 $\mathcal O(1)$。

总复杂度是 $\mathcal O(nm/B+zT+zB+nT)$，取 $B=\sqrt{nm/z}$ 可以得到复杂度是 $\mathcal O(\sqrt{nmz}+(n+z)T)$。