迁徙

最短路径结构

若路径出现局部折返，前后两点距离不超过其中一条边，可跳过折返点得到更短路径。因此最短路径严格自北向南。

用双指针求r[i]：从i一次最远可到的下标。r单调不减。固定起点，最短路第k层为(r^(k-1)(s),r^k(s)]。同层内某点的最短路条数，是上一层所有能到达它的点的路径条数之和；因r单调，贡献者构成上一层后缀，所以同层条数从左向右单调不增。

截断状态

只关心恰好2条，条数≥3可统一截为3。所有可达前驱至少贡献1，所以只需看上一层最右两点；若最右三个都能到达，条数必≥3。状态分三类：

• 0：最右点1条，倒数第二点也1条（若本层仅一个点，按此类处理）；
• 1：最右点1条，倒数第二点至少2条；
• 2：最右点2条。此时倒数第二点的具体数值不重要。

最右点已≥3时，后续所有层都≥3，可立即停止贡献。

令当前层为(p,z]，z=r[p]，下一层为(z,e]，e=r[z]。令w=z-p。状态2时，仅最后一个前驱贡献的区间才恰好2条，数量为e-max(z,r[z-1])；若w=1，则以z代替r[z-1]。状态0且w≥2时，恰好最后两个前驱贡献的区间才恰好2条，数量为max(0,r[z-1]-max(z,r[z-2]))；若w=2，以z代替r[z-2]。状态1无恰好2条的终点。

为了确定下一层状态，对e和e-1分别检查最右三个前驱是否覆盖：有三个则3；有两个则将两条数相加截为3；只有一个则继承最右条数。层大小由w与e-z可知。

动态规划

dp[p][state]表示当前层(p,r[p]]处于state时，后续所有层的双径终点数。转移到dp[r[p]][nextState]，再加本次贡献。r[p]>p时依赖下标更大，从右到左即可；不能向前推进时为0。

任意起点s的第一层每个点都只有一条直接路径，初始状态是0，所以答案是Σdp[s][0]。每个dp值≤n，可用int；总答案可能约10^12，必须long long。

时间O(N)，空间O(N)。独立oracle对无向距离图从每个起点BFS并计数，未复用本算法的分层三状态转移。大规模还核对了两条长链通过一个菱形连接的L*R解析答案。

难度依据

7 / geekpi-9-v2：利用最短路分层计数单调性，只保留最右两点的三类截断状态，在线性复杂度内统计所有起点。

参考程序

#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
struct Fast{static const int Z=1<<20;char b[Z];int p=0,n=0;char get(){if(p==n){n=fread(b,1,Z,stdin);p=0;if(!n)return 0;}return b[p++];}long long read(){char c;do c=get();while(c&&c<=32);bool neg=c=='-';if(neg)c=get();long long x=0;while(c>='0'&&c<='9'){x=x*10+c-'0';c=get();}return neg?-x:x;}}in;
int main(){in.read();int T=in.read();while(T--){int n=in.read();long long d=in.read();vector<long long>x(n);for(auto&v:x)v=in.read();vector<int>r(n);int j=0;for(int i=0;i<n;i++){j=max(j,i);while(j+1<n&&x[j+1]-x[i]<=d)j++;r[i]=j;}vector<array<int,3>>dp(n);long long ans=0;for(int p=n-1;p>=0;p--){int z=r[p],w=z-p,e=r[z],nw=e-z;if(w==0||nw==0)continue;for(int st=0;st<3;st++){int A=st==2?2:1;auto countAt=[&](int v){if(w>=3&&r[z-2]>=v)return 3;if(w>=2&&r[z-1]>=v)return st==0?2:3;return A;};int a=countAt(e),b=nw>=2?countAt(e-1):0,cnt=0;if(st==2)cnt=e-max(z,w>=2?r[z-1]:z);else if(st==0&&w>=2)cnt=max(0,r[z-1]-max(z,w>=3?r[z-2]:z));if(a<3)cnt+=dp[z][a==2?2:((b==0||b==1)?0:1)];dp[p][st]=cnt;}ans+=dp[p][0];}printf("%lld\n",ans);}}

本参考解为独立编写的训练参考解，非官方标准程序。测试数据为自建训练数据。