#482. [CSP-S 2026] 迁徙

[CSP-S 2026] 迁徙

迁徙(migrate)

CSP-S 2026 第二轮 · T3(赛题题意整理,测试数据为自制)

题目描述

有 nn 座岛屿排列在一条直线上,其坐标为严格递增的整数 x1<x2<⋯<xnx_1<x_2<\cdots<x_n。海鸟每次能从一座岛屿飞到另一座岛屿,当且仅当两岛坐标差的绝对值不超过 dd。每次飞行算路径的一步。

定义有序编号 u<vu<v 的一对岛屿为双径岛屿对,如果从 uu 到 vv 的最短路径恰好有两条。路径按完整经过的岛屿编号序列区分;不可达或最短路条数不是恰好两条都不计入答案。

对每组数据,求双径岛屿对的总数。

输入格式

第一行两个非负整数 c,tc,t,表示测试点编号和数据组数。cc 不影响算法。

随后 tt 组数据。每组第一行两个整数 n,dn,d;第二行给出 nn 个严格递增的整数 x1,…,xnx_1,\ldots,x_n。

输出格式

对每组数据输出一行整数:满足条件的岛屿对数量。

输入输出样例 #1

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

输入输出样例 #2

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

数据范围与说明

每个文件包含 2≤t≤1052\le t\le10^5 组数据;单组 1≤n≤2×1061\le n\le2\times10^6。一个测试文件的 N=∑n≤2×106N=\sum n\le2\times10^6。

1≤d≤2×10181\le d\le2\times10^{18},−1018≤x1<⋯<xn≤1018-10^{18}\le x_1<\cdots<x_n\le10^{18},0≤c≤250\le c\le25。

两条不同最短路径按经过的岛屿编号序列是否相同来区分。可能有三条以上最短路径,不能将它们误判成两条。

注意: Hydro 使用标准输入输出;测试数据自行生成,并非 CCF 官方测试数据。