解题思路

记 $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 & =b_i+[b_i>0]f_{l_i} \\ g_i & =c_i+[c_i>0]g_{r_i} \end{aligned}$$

其中 $[P]$ 为指示函数，$l_{n+1}=n+1,r_0=0$。非直接路径末两步记为 $h\to p\to i$；若 $p>l_i$，则 $h<l_i\le p-1$，以 $p-1$ 替换 $p$ 即得另一路。因此延伸恰要求 $p=l_i<i$ 且 $r_p=i$，即 $b_i>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}$，故：

$$s_a= \begin{cases} f_{a+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$$

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

$$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)$。

参考代码

698 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]=(j>i?l[i+1]:i)-l[i];
			if(f[i])f[i]+=f[l[i]];
		}
		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]=k-max(i,j);
			if(f[i])f[i]+=f[k];
			int a=l[i];
			if(a<i-1)ans+=1ll*(l[a+1]==l[a]?f[a+1]:l[a+2]-l[a+1])*(l[i+1]>a+1?f[i]+1:1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}