ABC384G Abs sum

· · 题解

锐评一下带 \log n 的官解有没有素质啊。

  • 给出长度为 n 的序列 a,b，q 次询问 x,y，求 \sum\limits_{i=1}^x\sum\limits_{j=1}^y|a_i-b_j|。

考虑以 B=\mathcal{O}(\sqrt n) 为块长分块。

预处理 F_{i,j} 表示 a 的前 i 块与 b 的前 j 块的答案。可以枚举 j，记块 j 的右端点为 r，然后指针 p 从 1 扫到 n，先维护好 b_1\sim b_j 的信息，p 每扫到一个新的值就查询 p 与 b_1\sim b_j 的贡献并统计。每扫到一个块的右端点就记录一下答案。

一共 \mathcal{O}(n) 次修改和 \mathcal{O}(n\sqrt n) 次查询，容易使用 \mathcal{O}(\sqrt n)-\mathcal{O}(1) 的分块维护。

剩余的贡献形如散块对一段前缀。注意到散块元素只有 \mathcal{O}(\sqrt n) 个，可以暴力累加所有元素的贡献。考虑把散块挂在前缀的右端点，扫描线维护前缀信息，然后遍历散块内的元素查询。同样使用 \mathcal{O}(\sqrt n)-\mathcal{O}(1) 的分块维护。注意到散块形如一个区间，因此直接在前缀右端点上挂一个区间即可。这样空间线性。

时间复杂度为 \mathcal{O}(n\sqrt n)，空间复杂度为 \mathcal{O}(n)。

AC Link & Code