自动搬运

查看原文

来自洛谷，原作者为

	koukilee 如果...有一天你死了，我也不会忘记你的。除非...这个世界，不再下雨。

搬运于2025-08-24 23:17:16，当前版本为作者最后更新于2025-05-06 16:55:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

需要求出 $|a_i - a_j| \leq \min(k_i, k_j)$ 的数对的数量。

发现这玩意有点类似于偏序，但是两种毫不相干的运算并不太好一起维护。

我们考虑能否固定等式两边的某一边，使得另一边好求呢？

显然是可以的，由于 $\min(k_i, k_j)$ 明显更好固定，我们选择固定这个。

于是先按照 $k$ 升序排序，这样第二维就是有序的。

所以对于一个 $i$ 我们要求的转化为：

$$\sum_{j = i}^n [|a_i - a_j| \le k_i] + \sum_{j = 1}^{i - 1} [|a_i - a_j| \le k_j] $$

发现加号左边的部分好维护。

如果我们将 $a$ 中 $i$ 后的值插入一颗值域线段树，就是需要求 $[a_i - k_i,a_i + k_i]$ 中一共出现了多少 $a_j$。

我们发现，如果 $i$ 对 $j$ 存在贡献的话，那么 $j$ 对 $i$ 同样也会有贡献。

那么右边部分，正是求 $i$ 对前面的贡献，所以我们需要求前面对 $i$ 的贡献即可。

只需要在前面处理 $j$ 的时候，将值域线段树 $[a_j - k_j,a_j + k_j]$ 整体加 $1$，最后再看 $a_i$ 处被加了多少次，就是 $i$ 对前面的贡献。

时间复杂度：$O(n\log V)$。

但是这样不一定能通过，考虑到一共只有 $n$ 个点，所以我们可以将权值离散化。

最后在求 $a_i - k_i$ 和 $a_i + k_i$ 的时候需要二分一下。

时间复杂度：$O(n\log n)$。