题解：AT_abc384_g [ABC384G] Abs Sum

FiraCode · 2024-12-15 21:30:01 · 题解

我们发现，这就是给你一个矩阵，第 i 行第 j 列的权值是 \left | A_i - B_j \right |，有 k 个询问，每次问你矩阵里 (1,1) 到 (x,y) 的和。

然后我么发现每个矩阵都有一个 (1, 1) 固定，只有 (x,y) 在变，所以就直接类似一维莫队，然后维护两个权值线段树，一个维护当前扫到的所有 B_j，另一个维护当前扫到的所有 A_i。

然后考虑新加一个 x + 1，那么就是说多了 \sum \left | A_{x + 1} - B_j \right |，那么就把绝对值拆开，然后就是在维护 B 的权值线段树上，查 \le A_{x + 1} 的 B_j 的和以及数量，以及 > A_{x + 1} 的 B_j 的和以及数量，然后删除和关于 y 的类似，然后就做完了。