4517. 迁徙

【题目描述】

海上有n 座岛屿，自北向南排成一条直线，其中第i (1 ≤ i ≤ n) 座岛屿在这条直线上的坐标为整数xi，且x 1  < x2  < ··· < xn。每年秋季，一群海鸟会沿着这条直线在南北方向上迁徙，小P 正在观察它们。

海鸟的体力有限，每次飞行的距离都不超过d。若两座岛屿i,j (1 ≤ i,j ≤ n) 满足|xi −xj | ≤ d，海鸟就可以从第i 座岛屿直接飞到第j 座岛屿。

对于两座不同的岛屿u,v (1 ≤ u,v ≤ n)，一条从第u 座岛屿到第v 座岛屿的路径形如y 1  → y2  → ··· → ym，其中y 1  = u，ym = v，且对于所有l (1 ≤ l ≤ m − 1)，海鸟都能够从第yl  座岛屿直接飞到第yl+1  座岛屿；其长度为m − 1，即海鸟在路径中飞行的次数。

小P 发现，海鸟在迁徙时总是会选择长度最短的路径。对于两座岛屿u,v (1 ≤ u < v ≤ n)，若从第u 座岛屿到第v 座岛屿的长度最短的路径恰好有两条，海鸟可以分成两群，分别沿其中一条飞往第v 座岛屿；此时称(u,v) 为双径岛屿对。两条路径不同，当且仅当它们经过的岛屿序列不完全相同。你需要帮助小P 求出双径岛屿对的数量。

【输入格式】

从文件migrate.in 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数c,t，分别表示测试点编号与测试数据组数。特别地，若c = 0，则该测试点为样例。

接下来依次输入t 组测试数据。对于每组测试数据：

• 第一行包含两个正整数n,d，分别表示岛屿数量和海鸟一次最多能飞行的距离。

• 第二行包含n 个严格递增的整数x 1 ,x2 ,    ,xn，依次表示每座岛屿的坐标。

【输出格式】

输出到文件migrate.out 中。对于每组测试数据，输出一行一个非负整数，表示双径岛屿对的数量。

【样例1输入】

0 2
4 2
1 2 3 4
5 2
1 2 3 4 5

【样例1输出】

1
2
1
2

【样例1说明】

该样例共包含两组测试数据。

对于第一组测试数据，共有0 个双径岛屿对。从第1 座岛屿到第5 座岛屿有三条长度最短的路径，分别为1 → 2 → 5，1 → 3 → 5 和1 → 4 → 5，因此(1 ,5) 不是双径岛屿对。对于第二组测试数据，仅有1 个双径岛屿对(1 ,4)。从第1 座岛屿到第4 座岛屿有两条长度最短的路径，分别为1 → 2 → 4 和1 → 3 → 4。第5 座和第6 座岛屿均无法到达任何其他岛屿。

【样例2输入】

0 2
5 3
-2 -1 0 1 2
6 2
-4 -3 -2 -1 3 6

【样例2输出】

0
1

【样例2说明】

该样例共包含两组测试数据。

对于第一组测试数据，仅有1 个双径岛屿对(1 ,4)。从第1 座岛屿到第4 座岛屿有两条长度最短的路径，分别为1 → 2 → 4 和1 → 3 → 4。对于第二组测试数据，共有2 个双径岛屿对，分别为(1 ,4) 和(2 ,5)。从第1 座岛屿到第5 座岛屿只有一条长度最短的路径1 → 3 → 5，因此(1 ,5) 不是双径岛屿对。

【数据规模与约定】

【来源】

在此键入。