Good Pairs

题意翻译

给定一个 $n$ 个数的序列 $a$ 和一个数 $k$，定义一个 **子区间** $[l,r]$ 是好的，当且仅当这个区间内存在一个 **子序列** 满足： - 包含 $a_l$ 和 $a_r$ - 任意相邻两个数差的绝对值不超过 $k$ 请求出所有合法的子区间数量。多组数据，$1\le \sum n\le 5\times 10^5,\ 0\le k\le 10^5,\ 1\le a_i\le 10^5$。

题目描述

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

6
9
18
92

说明

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.

**题目大意：**

给定一个包含 $ n $ 个整数的数组 $ a $ 和一个整数 $ k $ 。定义一个子区间 $[l, r]$ 是好的，如果存在一个子序列满足以下条件：

- 包含 $ a_l $ 和 $ a_r $
- 序列中任意相邻两个数的差的绝对值不超过 $ k $

求出所有合法的子区间数量。

**输入数据格式：**

输入包含多个测试用例。第一行包含一个整数 $ t $ （$ 1 \leq t \leq 10^5 $），表示测试用例的数量。每个测试用例包含两行：

- 第一行包含两个空格分隔的整数 $ n $ 和 $ k $ （$ 1 \leq n \leq 5 \times 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 \times 10^5 $。

**输出数据格式：**

对于每个测试用例，输出一个整数，表示好的子区间数量。

**输入输出样例：**

**输入样例 #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：**
```
6
9
18
92
```**题目大意：** 给定一个包含 $ n $ 个整数的数组 $ a $ 和一个整数 $ k $ 。定义一个子区间 $[l, r]$ 是好的，如果存在一个子序列满足以下条件： - 包含 $ a_l $ 和 $ a_r $ - 序列中任意相邻两个数的差的绝对值不超过 $ k $ 求出所有合法的子区间数量。 **输入数据格式：** 输入包含多个测试用例。第一行包含一个整数 $ t $ （$ 1 \leq t \leq 10^5 $），表示测试用例的数量。每个测试用例包含两行： - 第一行包含两个空格分隔的整数 $ n $ 和 $ k $ （$ 1 \leq n \leq 5 \times 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 \times 10^5 $。 **输出数据格式：** 对于每个测试用例，输出一个整数，表示好的子区间数量。 **输入输出样例：** **输入样例 #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：** ``` 6 9 18 92 ```