解题思路

为了正确统计满足条件的下标对 (i,j) 且 i < j，我们需要：

1. 保持原始数组的下标关系
2. 对于每个元素 A[j]，统计前面有多少个元素 A[i] (i < j) 满足 A[i] - A[j] ≥ K

可以采用以下方法：

• 使用归并排序的思想，在排序过程中统计满足条件的对数

题目内容

给定一个整数数组 $A$，长度为 $n$ 。在给定一个整数 $K$ ，定义下标对 $(i,j)$(满足$i＜j$)，如果 $A[i]-A[j]≥K$，为「K-统治对」。

统计并返回数组中所有「K-统治对」的数量。

输入描述

数组长度 $n$ ；范围 $[1,100000]$

数组各元素，用空格分隔，元素取值范围 $[-100000,100000]$

整数 $K$

输出描述

输出一个整数，表示数组中所有「K-统治对」的数量。

样例1

输入

5
-3 -1 -6 2 0
2

输出

3

说明

满足 $A[i]-A[j]>=2$ 且 $i<j$ 的下标对如下：

$(0,2):-3-(-6)=3>=2$

$(1,2):-1-(-6)=5 >= 2$

$(3,4):2-0=2>= 2$

故最终计数为 $3$ 。

样例2

输入

5
2 9 4 7 1
2

输出

5

说明

满足 $A[i]-A[j]>=2$ 且 $i<j$ 的下标对如下：

$(1,2):9-4=5>=2$

$(1,3):9-7=2 >= 2$

$(1,4):9-1=8>=2$

$(2,4):4-1=3 >= 2$

$(3,4):7-1=6 >= 2$

共计 $5$ 个。