看到这道题，很容易想到枚举 x，再去找 y，这样一个暴力代码就诞生了，这样会超时，所以我们就来介绍一下二分做法：
问题转换 ：
对于每对垂直线段 a[i] 和 a[j]（i < j），水平距离 s = a[j] - a[i]。
垂直距离 d 需满足 |s - d| = k，即 d = s + k 或 d = s - k。
每个有效 d 对应的点对数为 m - d + 1。
核心公式 ：
对于 d = s + k，有效 a[i] 范围为 [max(1, a[j] + k - m), a[j] + k - 1]。
对于 d = s - k，有效 a[i] 范围为 [max(1, a[j] - k - m), a[j] - k - 1]。
优化策略 ：
使用前缀和数组 s 快速计算范围内 a[i] 的总和。
二分查找确定有效 a[i] 的范围，避免遍历所有可能的 i。
实现细节
数组索引 ：
采用 0-based-1 索引（ a[0] 到 a[n-1] ），前缀和数组 s 同步调整。
前缀和 s[i] 表示 a[0] 到 a[i-1] 的和。
二分查找 ：
lower_{}bound(a , a + j, L) 返回第一个 >= L 的位置。
upper_{}bound(a , a + j, R) 返回第一个 >R 的位置，需减 1 得到最后一个 <= R 的位置。
条件判断 ：
对于每个 j，检查 L1 <= R1 和 L2 <= R2 确保范围有效。
使用 itl <= itr 验证二分查找结果是否构成有效区间。
贡献计算 ：
对于每个有效范围 [itl, itr]，总和为 $s[itr + 1] - s[itl]（前缀和）加上固定贡献 (m - a[j] ± k + 1) * (itr - itl + 1)$。
复杂度分析
- 时间复杂度 ：O (nlogn)
- 遍历每个 j 需要 O(n)。
- 每次遍历中，二分查找和前缀和计算为 O(log n)。
核心逻辑总结
- 枚举线段：对于每个线段 j，考虑所有 i<j。
- 计算范围：根据 d=s+k 和 d=s−k 分别确定 a[i] 的有效范围。
- 二分查找：快速定位有效 i 的区间，避免遍历所有可能的 i。
- 前缀和优化：利用前缀和数组快速计算区间和，减少时间复杂度。
该算法通过数学推导和预处理，将时间复杂度从 O(n^2) 优化至 O(nlogn)，适用于大规模数据。
这样这道题就做完了。
完结撒花 ✿✿ヽ(°▽°)ノ✿
