解题思路

记 $l_i,r_i$ 为从 $i$ 一步可达的最左、最右岛屿，包含自身。

最短路严格递增，起点右侧各层按坐标分离。两路若至少两层不同，逐层取最大、最小路径再由大转小拼接，可得第三路；同层两点不相邻时，夹点也产生第三路。故恰好两路仅有单个相邻菱形：

$$p\to\set{a,a+1}\to q,p<a<a+1<q,r_p=a+1,l_q=a$$

记 $f_i$ 为到 $i$ 的最短路唯一且每步均跳至最右可达点的起点数，包含 $i$；$g_i$ 为反向对称量。直接起点数与递推为：

$$\begin{aligned} b_i & =\min(i,l_{i+1})-l_i \\ c_i & =r_i-\max(i,r_{i-1}) \\ f_i & =1+b_i+[b_i>0](f_{l_i}-1) \\ g_i & =1+c_i+[c_i>0](g_{r_i}-1) \end{aligned}$$

其中 $[P]$ 为指示函数，$l_{n+1}=n+1,r_0=0$；非直接起点要求前驱唯一，才可继续延伸。

固定 $q$，令 $a=l_q<q-1$。此时 $l_{a+2}\le a$，可选前驱为 $[l_{a+1},l_{a+2})$；额外左延伸仅来自 $p=l_a=l_{a+1}$。相等时，直接前驱与额外延伸恰好合成 $f_{a+1}-1$，故：

$$s_a= \begin{cases} f_{a+1}-1 & l_{a+1}=l_a \\ l_{a+2}-l_{a+1} & l_{a+1}>l_a \end{cases}$$

右延伸要求 $r_{a+1}=q$，等价于 $l_{q+1}>a+1$，因此：

$$R_q=1+[l_{q+1}>a+1](g_q-1)$$

两侧边界被强制后，路径最短且仅在菱形处分叉，左右独立，答案为：

$$A=\sum_{\substack{1\le q\le n\\l_q<q-1}}s_{l_q}R_q$$

利用 $l$ 的单调性逆向恢复 $r$；逆扫时 $a+1<q$，可在同一数组中以 $g$ 覆盖 $f$。时间、空间复杂度均为 $O(n)$。

参考代码

710 Bcpp

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

using ll=long long;
const int N=2000005;
ll x[N];
int l[N],f[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;
			}
			f[i]=1+(j>i?l[i+1]:i)-l[i];
			if(f[i]>1)f[i]+=f[l[i]]-1;
		}
		l[n+1]=n+1;
		ll ans=0;
		for(int i=n;i>=1;i--)
		{
			int k=j;
			while(l[j]==i)j--;
			f[i]=1+k-max(i,j);
			if(f[i]>1)f[i]+=f[k]-1;
			int a=l[i];
			if(a<i-1)ans+=1ll*(l[a+1]==l[a]?f[a+1]-1:l[a+2]-l[a+1])*(l[i+1]>a+1?f[i]:1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}