一、分析
由于要求必须是最短路，所以飞行方向一定是从左向右的
从“恰好两条最短路径”入手，查看两条路径是否有什么特点
-
设两条最短路径分别为：
- $P:p_1,p_2\cdots p_n~~~Q:q_1,q_2\cdots q_n $ ，\(P,Q\) 长度、起点和终点都相同
- 设 \(P,Q\) 第一个不相同的位置是 \(i\) ，且 \(p_i，则 \(p_{i-1}=q_{i-1}\)
- 那么 \(q_i 一定成立，否则，由于 \(q_{i-1}\) 能够直接到达 \(q_i\) ，那么一定能够直接到达 \(p_{i+1}\) ，从而不用经过 \(p_i\) ，路径 \(P\) 就不是最短路。因此 \(p_i
- 那么路径 \(p_1,\cdots,p_{i-1},q_i,p_{i+1},\cdots,p_n\) 也是合法最短路径，而若 \(P,Q\) 序列若后面还有不相同的则会有第三条最短路
- 结论：“恰好有两条最短路”时，只有一个位置不同**
-
两条最短路径的共同前驱记为 \(p\) ，后继记为 \(q\) ,中间两个不同的点分别为 \(a,b~(a 。若 \(a,b\) 之间还有其他的岛屿，则这个岛屿既能被 \(p\) 到达，也能到达 \(q\) ，则这条起点到终点就有三条最短路。因此 \(b=a+1\)
设分叉点的前驱为 \(p\) ，后继为 \(q\) ，\(l_i,r_i\) 分别表示点 \(i\) 向左和向右能够到达的最远的点，所有分叉点的范围为 \([l_q,r_p]\)，在范围内选择两个点 \(a,a+1\) ，而由于“只有两条最短路”的条件，因此 \(\bf {l_q=a,r_p=q+1}\)
枚举分叉以外的点 \(i\to j\) 满足 \(r_i=j.l_j=i\)
预处理出每个点的前缀和后缀数量 ：
-
\(f_p\) 表示有多少个不同起点，可以按每次走 \(r_j\) 的方式到达 \(p\)
-
\(g_i\) 表示每次有多少个不同终点，可以按每次走 \(l_j\) 的方式到达 \(q\)
设 \(A_a,B_a\) 表示分叉为 \(a,a+1\) 表示对应的可以作为起点和终点的数量
最终的答案为 \(ans=\sum_\limits a A_aB_a\)
每次 \(O(n)\) 枚举分叉点 \(a\)
时间复杂度为 \(O(n)\)
二、\(\text{code}\)
#include
#define int long long
using namespace std;
const int N=2e6+5;
int c,T,n,d,x[N],l[N],r[N],p1,p2,f[N],A[N],a,ans,sum;
//f[p]=有多少个不同起点，可以按规定的方式到达 p
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>c>>T;while(T--){cin>>n>>d;for(int i=1;i<=n;i++)cin>>x[i];memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(f,0,sizeof(f));memset(A,0,sizeof(A));ans=0;p1=1,p2=1;for(int i=1;i<=n;i++){while(x[i]-x[p1]>d) p1++;l[i]=p1;if(p2=a) continue;A[a]++;if(l[a]==p)A[a]+=f[p];}memset(f,0,sizeof(f));//f[q]:能接到 q 后的合法终点数 for(int i=n;i>=1;i--){int j=l[i];if(j==i) continue;f[j]++;if(r[j]==i)f[j]+=f[i];}//分叉后继 q for(int q=1;q<=n;q++){a=l[q];//分叉为 a if(q<=a+1) continue;sum=1;if(r[a+1]==q)sum+=f[q];ans=ans+A[a]*sum;}cout<