2906 - 【入门】相互认识

在某国，有 n 户渔民住在海岸线上，整齐的排列成一条直线。每个渔民的房子我们用一个坐标 p_i 来表示，每个渔民的活动半径为 d。也就是说两个距离小于等于 d 的房子，这两户渔民相互认识。

那么在某国，有多少对渔民相互认识？

第一行输入两个整数 n\ (1 \le n \le 10^5)，d\ (1 \le d \le 10^4)，两数之间以一个空格分隔。

第二行输入 n 个整数 p_i\ (1 \le p_i \le 10^{8})，表示每个渔民房子的坐标（存在坐标相同的 p_i），相邻两数之间以一个空格分隔。

输出一个整数，表示有多少对渔民相互认识。

直接两两比较每个渔民之间距离，时间复杂度为 \mathcal{O}(n^2)，肯定过不了本题。

排序后，对每个渔民 i，统计他右边有多少户渔民和他距离小于等于 d，代码中的 pos 表示右边第一个距离 >d 的位置。

时间复杂度 \mathcal{O}(nlogn)。