CF1762F.Good Pairs

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given an array $a$ consisting of $n$ integers and an integer $k$ .

A pair $(l,r)$ is good if there exists a sequence of indices $i_1, i_2, \dots, i_m$ such that

$i_1=l$ and $i_m=r$ ;
$i_j < i_{j+1}$ for all $1 \leq j < m$ ; and
$|a_{i_j}-a_{i_{j+1}}| \leq k$ for all $1 \leq j < m$ .

Find the number of pairs $(l,r)$ ( $1 \leq l \leq r \leq n$ ) that are good.

输入格式

Each test contains multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 10^5$ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space-separated integers $n$ and $k$ ( $1 \leq n \leq 5 \cdot 10^5$ ; $0 \leq k \leq 10^5$ ) — the length of the array $a$ and the integer $k$ .

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ( $1 \leq a_i \leq 10^5$ ) — representing the array $a$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$ .

输出格式

For each test case, print the number of good pairs.

输入输出样例

输入#1

4
3 0
1 1 1
4 2
4 8 6 8
6 4
7 2 5 8 3 8
20 23
110 57 98 14 20 1 60 82 108 37 82 73 8 46 38 35 106 115 58 112

输出#1

说明/提示

In the first test case, good pairs are $(1,1)$ , $(1,2)$ , $(1,3)$ , $(2,2)$ , $(2,3)$ , and $(3,3)$ .

In the second test case, good pairs are $(1,1)$ , $(1,3)$ , $(1,4)$ , $(2,2)$ , $(2,3)$ , $(2,4)$ , $(3,3)$ , $(3,4)$ and $(4,4)$ . Pair $(1,4)$ is good because there exists a sequence of indices $1, 3, 4$ which satisfy the given conditions.

首页