CF1762F Good Pairs

给定一个由 $n$ 个整数构成的数组 $a$ 和一个整数 $k$。 如果存在一组下标序列 $i_1, i_2, \dots, i_m$，使得： - $i_1 = l$ 且 $i_m = r$； - 对所有 $1 \leq j < m$，都有 $i_j < i_{j+1}$； - 对所有 $1 \leq j < m$，都有 $|a_{i_j} - a_{i_{j+1}}| \leq k$， 则称一对 $(l, r)$ 是“好对”。 请你求出有多少对 $(l, r)$（$1 \leq l \leq r \leq n$）是“好对”。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试数据的组数。每组测试数据的描述如下： 每组的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 5 \cdot 10^5$，$0 \leq k \leq 10^5$），分别表示数组 $a$ 的长度和整数 $k$。 每组的第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^5$），表示数组 $a$。 保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每组测试数据，输出“好对”的数量。

在第一个测试点中，“好对”有 $(1,1)$、$(1,2)$、$(1,3)$、$(2,2)$、$(2,3)$ 和 $(3,3)$。 在第二个测试点中，“好对”有 $(1,1)$、$(1,3)$、$(1,4)$、$(2,2)$、$(2,3)$、$(2,4)$、$(3,3)$、$(3,4)$ 和 $(4,4)$。例如，$(1,4)$ 是“好对”，因为存在下标序列 $1, 3, 4$ 满足条件。 由 ChatGPT 4.1 翻译