题解：P11930 [PA 2025] 吃树叶 / Liście

· · 题解

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

操作是维护 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)。