题解：P12670 「TFXOI Round 2」LQXZ & AGLT

· · 题解

需要求出 |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)。