解题思路

记 $l_i,r_i$ 为与 $i$ 距离不超过 $d$ 的最左、最右岛屿，包含 $i$ 本身。两数组单调不减，可用双指针求出。

最短路径严格递增。否则删除一个局部极值点后，相邻两点距离仍不超过 $d$，与路径最短矛盾。

从 $u$ 连续跳向最右可达岛屿，记第 $k$ 次跳跃后为 $b_k$。在 $u$ 及其右侧，至多跳跃 $k$ 次可到达的岛屿恰好构成 $[u,b_k]$，所以最短路径第 $k$ 层位于 $(b_{k-1},b_k]$，不同层严格分离。

考虑两条不同最短路径。每层分别取较小、较大的岛屿，仍构成合法路径；从某层较大点跳向下一层较小点也合法，因为距离只会缩短。若至少两层不同，在这两层之间从较大路径切换到较小路径，就得到第三条路径。因此，恰好两条最短路径仅在一层不同。该层的两个点必须相邻，否则夹在中间的点也能替换，产生第三条路径。

设分叉点为 $a,a+1$，共同前驱、后继为 $p,q$。可作 $p$ 到 $q$ 中间点的区间为 $[l_q,r_p]$，故恰好有：

$$p<a<a+1<q,r_p=a+1,l_q=a$$

记 $f_{i,0}$ 为满足以下条件的左端点 $u$ 的数量，包含 $u=i$：从 $u$ 到 $i$ 的最短路径唯一；连续向最右岛屿跳跃，在最短路径长度对应的次数后恰好到达 $i$。

设最后一次跳跃前为 $j$，有 $r_j=i$。$u=j$ 时直接贡献 $1$；$u<j$ 时，设上一层最右可达点为 $k$，由 $r_k=j<i$ 可知 $k<l_i$，故本层可能的前驱恰为 $[l_i,j]$。唯一性要求 $l_i=j$，且此前路径唯一。令 $l_{n+1}=n+1$，由 $\#\set{j<i\mid r_j=i}=\min(i,l_{i+1})-l_i$，得到：

$$f_{i,0}=1+\min(i,l_{i+1})-l_i+ \begin{cases} f_{l_i,0}-1 & l_i<i\land r_{l_i}=i \\ 0 & \text{otherwise} \end{cases}$$

减去的 $1$ 对应已经统计的 $u=l_i$。对称定义 $f_{i,1}$，统计最短路径唯一，且从 $v$ 向最左连续跳跃恰好到达 $i$ 的右端点 $v$，包含 $v=i$。令 $r_0=0$，得到：

$$f_{i,1}=1+r_i-\max(i,r_{i-1})+ \begin{cases} f_{r_i,1}-1 & r_i>i\land l_{r_i}=i \\ 0 & \text{otherwise} \end{cases}$$

两式分别从左向右、从右向左计算。

固定分叉 $a,a+1$。若左端点在 $p$ 左侧，$p$ 必须为该层最右可达点，而能飞往 $a$ 的前驱恰为 $[l_a,p]$，故必须有 $l_a=p$。反之，这一条件把两条分支的前驱都强制为 $p$。右侧同理：若终点在 $q$ 右侧，必须且仅须 $r_{a+1}=q$，将分叉后的共同点强制为 $q$。

令 $[P]$ 为命题 $P$ 的指示函数。包含不延伸的情况，两侧权值为：

$$\begin{aligned} L_p & =1+[l_a=p](f_{p,0}-1) \\ R_q & =1+[r_{a+1}=q](f_{q,1}-1) \end{aligned}$$

这些限制同时保证最短性：左侧贪心链先到达 $p$，再到达 $a+1$；右侧发生延伸时，下一步恰好到达 $q$。结合 $f_{q,1}$ 的定义，剩余距离无法缩短。反向同理，所以两侧唯一段之间恰好保留 $a,a+1$ 两个选择，权值可以独立相乘。

按 $a$ 汇总左侧，再枚举 $q$，答案为：

$$\begin{aligned} s_a & =\sum_{\substack{p<a\\r_p=a+1}}L_p \\ A & =\sum_{\substack{1\le q\le n\\l_q+1<q}}s_{l_q}R_q \end{aligned}$$

每对双径岛屿仅有一个分叉位置，因此不会重复统计。时间复杂度 $O(n)$，空间复杂度 $O(n)$。

参考代码

791 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=2000005;
ll x[N];
int l[N],r[N],f[N],s[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int c,T;
	cin>>c>>T;
	while(T--)
	{
		int n;
		ll d;
		cin>>n>>d;
		for(int i=1;i<=n;i++)cin>>x[i];
		int j=0;
		for(int i=1;i<=n;i++)
		{
			while(j<n&&x[j+1]-x[i]<=d)
			{
				j++;
				l[j]=i;
			}
			r[i]=j;
			s[i]=0;
		}
		l[n+1]=n+1;
		for(int i=1;i<=n;i++)
		{
			f[i]=1+min(i,l[i+1])-l[i];
			if(l[i]<i&&r[l[i]]==i)f[i]+=f[l[i]]-1;
			if(r[i]>i+1)s[r[i]-1]+=l[r[i]-1]==i?f[i]:1;
		}
		r[0]=0;
		ll ans=0;
		for(int i=n;i>=1;i--)
		{
			f[i]=1+r[i]-max(i,r[i-1]);
			if(r[i]>i&&l[r[i]]==i)f[i]+=f[r[i]]-1;
			if(l[i]<i-1)ans+=1ll*s[l[i]]*(r[l[i]+1]==i?f[i]:1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}