题解：P17833 [CSP-S 2026] 迁徙 / migrate（民间数据）

Yuneko · 2026-11-01 17:38:41 · 题解

太深刻了 bro。

题意就是数最短路数量 = 2 的点对 (i,j) 数量。

先双指针预处理出每个点 i 往左跳能到达的最左端点 lst_i 和往右跳能到达的最右端点 nxt_i。

考虑 dp，设 f_i 表示目前走到 i 并且合法路径数恰好为 1 的左端点数量，g_i 表示目前走到 i 并且合法路径数恰好为 2 的左端点数量，h_i 表示目前走到 i-1,i 的合法路径数都恰好为 1 的左端点数量（走到 i+1 的最短路长度和 i 不同）。

可以直接分讨进行转移，不过细节不算很少，具体可以看代码。

时间复杂度 O(n)。

ll n,m,L,R,ans;
ll a[2000010],f[2000010],g[2000010],h[2000010];
ll lst[2000010],nxt[2000010];
void solve(){
    L=R=1,ans=0;
    cin>>n>>m;
    forl(i,1,n) cin>>a[i];
    forl(i,1,n){
        f[i]=g[i]=h[i]=0;
        while(R<n && a[R+1]-a[i]<=m) R++;
        while(a[i]-a[L]>m) L++;
        nxt[i]=R,lst[i]=L;
    }
    forl(i,1,n){
        ll l=lst[i],r=nxt[i];
        if(l<i) ans+=g[l];
        if(l+1<i) ans+=h[l+1];
        if(i==r) continue;
        f[r]++;
        if(lst[r]==i) f[r]+=f[i],g[r]+=g[i];
        if(lst[r]==i-1) g[r]+=h[i];
        if(r-1>i){
            h[r]++;
            if(lst[r-1]==i) h[r]+=f[i];
        }
    }
    cout<<ans<<endl;
}