P17833 [CSP-S 2026] 迁徙 / migrate（民间数据）

海上有 $n$ 座岛屿，自北向南排成一条直线，其中第 $i$（$1 \le i \le n$）座岛屿在这条直线上的坐标为整数 $x_i$，且 $x_1 < x_2 < \cdots < x_n$。每年秋季，一群海鸟会沿着这条直线在南北方向上迁徙，小 P 正在观察它们。 海鸟的体力有限，每次飞行的距离都不超过 $d$。若两座岛屿 $i,j$（$1 \le i,j \le n$）满足 $|x_i-x_j| \le d$，海鸟就可以从第 $i$ 座岛屿直接飞到第 $j$ 座岛屿。 对于两座不同的岛屿 $u,v$（$1 \le u,v \le n$），一条从第 $u$ 座岛屿到第 $v$ 座岛屿的路径形如 $y_1 \to y_2 \to \cdots \to y_m$，其中 $y_1=u$，$y_m=v$，且对于所有 $l$（$1 \le l \le m-1$），海鸟都能够从第 $y_l$ 座岛屿直接飞到第 $y_{l+1}$ 座岛屿；其长度为 $m-1$，即海鸟在路径中飞行的次数。 小 P 发现，海鸟在迁徙时总是会选择长度最短的路径。对于两座岛屿 $u,v$（$1 \le u < v \le n$），若从第 $u$ 座岛屿到第 $v$ 座岛屿的长度最短的路径**恰好**有两条，海鸟可以分成两群，分别沿其中一条飞往第 $v$ 座岛屿；此时称 $(u,v)$ 为**双径岛屿对**。两条路径不同，当且仅当它们经过的岛屿序列不完全相同。 你需要帮助小 P 求出双径岛屿对的数量。

从文件 `migrate.in` 中读入数据。 **本题包含多组测试数据。** 输入的第一行包含两个非负整数 $c,t$，分别表示测试点编号与测试数据组数。特别地，若 $c=0$，则该测试点为样例。 接下来依次输入 $t$ 组测试数据。对于每组测试数据： - 第一行包含两个正整数 $n,d$，分别表示岛屿数量和海鸟一次最多能飞行的距离。 - 第二行包含 $n$ 个严格递增的整数 $x_1,x_2,\ldots,x_n$，依次表示每座岛屿的坐标。

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

### 样例 1 解释 该样例共包含两组测试数据。 对于第一组测试数据，仅有 $1$ 个双径岛屿对 $(1,4)$。从第 $1$ 座岛屿到第 $4$ 座岛屿有两条长度最短的路径，分别为 $1 \to 2 \to 4$ 和 $1 \to 3 \to 4$。 对于第二组测试数据，共有 $2$ 个双径岛屿对，分别为 $(1,4)$ 和 $(2,5)$。从第 $1$ 座岛屿到第 $5$ 座岛屿只有一条长度最短的路径 $1 \to 3 \to 5$，因此 $(1,5)$ 不是双径岛屿对。 ### 样例 2 解释 该样例共包含两组测试数据。 对于第一组测试数据，共有 $0$ 个双径岛屿对。从第 $1$ 座岛屿到第 $5$ 座岛屿有三条长度最短的路径，分别为 $1 \to 2 \to 5$，$1 \to 3 \to 5$ 和 $1 \to 4 \to 5$，因此 $(1,5)$ 不是双径岛屿对。 对于第二组测试数据，仅有 $1$ 个双径岛屿对 $(1,4)$。从第 $1$ 座岛屿到第 $4$ 座岛屿有两条长度最短的路径，分别为 $1 \to 2 \to 4$ 和 $1 \to 3 \to 4$。第 $5$ 座和第 $6$ 座岛屿均无法到达任何其他岛屿。 ### 样例 3 见题目目录下的 `migrate/3.in` 与 `migrate/3.ans`。 该样例满足测试点 $3 \sim 6$ 的约束条件。 ### 样例 4 见题目目录下的 `migrate/4.in` 与 `migrate/4.ans`。 该样例满足测试点 $11,12$ 的约束条件。 ### 样例 5 见题目目录下的 `migrate/5.in` 与 `migrate/5.ans`。 该样例满足测试点 $15 \sim 18$ 的约束条件。 ### 样例 6 见题目目录下的 `migrate/6.in` 与 `migrate/6.ans`。 该样例满足测试点 $19 \sim 21$ 的约束条件。 ### 数据范围 设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有： - $0 \le c \le 25$，$2 \le t \le 10^5$； - $1 \le n \le 2 \times 10^6$，$N \le 2 \times 10^6$，$1 \le d \le 2 \times 10^{18}$； - $-10^{18} \le x_1 < x_2 < \cdots < x_n \le 10^{18}$。 ::cute-table{tuack} | 测试点编号 | $N \le$ | 特殊性质 | | :---: | :---: | :---: | | $1,2$ | $9$ | 无 | | $3 \sim 6$ | $300$ | ^ | | $7 \sim 10$ | $5000$ | ^ | | $11,12$ | $2 \times 10^6$ | A | | $13,14$ | ^ | B | | $15 \sim 18$ | $10^6$ | C | | $19 \sim 21$ | $2 \times 10^5$ | 无 | | $22 \sim 25$ | $2 \times 10^6$ | ^ | 特殊性质 A：$x_1,x_2,\ldots,x_n$ 构成等差数列。 特殊性质 B：存在一座岛屿，使得海鸟可以从该岛屿直接飞到任意其他岛屿。 特殊性质 C：$x_n-x_1 \le 10d$。