战斗爽！

设 \(prv_i,nxt_i\) 表示从点 \(i\)

向左/向右跳能跳到的最远的点。

考察一对合法的 \(u,v\)，显然从 \(u\) 向右贪心跳到 \(v\) 是一条合法路径 \(a_1,\cdots,a_k\)。对于另一条路径 \(b_1,\cdots,b_k\)，取最小的 \(i\) 使得 \(a_i>b_i\)，则 \(a_i,b_i\) 到 \(v\)

的最短路径都是唯一的。

这启发我们去刻画 \(u,v\) 间最短路唯一的条件。运用一些注意力，观察到 \(u,v\) 间最短路唯一，当且仅当：从 \(u\) 出发向右贪心跳的路径，和从 \(v\) 出发向左贪心跳的路径完全相同。设向左贪心跳的路径反转后为 \(b_1,\cdots,b_k\)，则对于任意合法最短路 \(c_1,\cdots,c_k\)，不难发现 \(b_i\leq c_i\leq a_i\)

，由此得证。

继续刻画 \(u,v\) 间恰好有两条最短路的条件。观察到 \(a_1,\cdots,a_i,b_{i+1},\cdots,b_k\) 同样是合法的最短路，因此如果 \(a,b\) 在至少两个位置 \(p 不同，则 \(a_1,\cdots,a_p,b_{p+1},\cdots,b_k\) 是第三条最短路，不合法。而若 \(a_i-b_i>1\)，显然也可以取它们中间的点得到第三条最短路。

于是我们得到了 \(u,v\) 间恰好有两条最短路充要条件：存在一个 \(i\)，使得 \(a_i-b_i=1\)，且对于每个 \(j\neq i\)，\(a_j=b_j\)

。

考虑枚举 \(b_i=x\)，设 \(x\) 所在的路径向左走一步到达 \(u\)，\(x+1\) 所在路径向右走一步到达 \(v\)。显然要有 \(nxt_u=x+1\)。若 \(prv_x，则 \(u\) 必须是路径起点；若 \(u=prv_x\)，则 \(u\) 能贡献到的路径起点 \(s\) 需要满足：\(s\) 向右贪心跳恰好能跳到 \(u\)，且 \(s\) 到 \(u\) 的最短路唯一。设 \(f_i\) 表示 \(i\) 能贡献到的路径起点的个数，容易分讨得到 DP 转移：

\[f_i=1+\sum_{prv_i

正序枚举 \(i\)，维护 \((prv_i,i)\)

区间内的桶即可。

类似设 \(g_i\) 表示 \(i\)

能贡献到的路径终点的个数：

\[g_i=1+\sum_{ii\land prv_{nxt_i}=i]g_{nxt_i} \]

倒序枚举 \(i\)，维护 \((i,nxt_i)\)

区间内的桶即可。

一个 \(x\)

对应的路径起点的个数为

\[\sum_{prv_i

对应的路径终点的个数为

\[\sum_{i+1i+1\land prv_{nxt_{i+1}}=i]g_{nxt_{i+1}} \]

两个 \(\sum\) 可以在计算 \(f,g\)

的时候顺便得到。

时间复杂度 \(\mathcal{O}(n)\)

。

复现了一下场上代码。不算太难写。

代码
#include using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair;
const int MAXN = 2e6 + 5;template T lowbit(T x) { return x & -x; }
template void chkMin(T &x, T y) { x = y < x ? y : x; }
template void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }int tid, tc, n, prv[MAXN], nxt[MAXN];
int f[MAXN], g[MAXN], buc[MAXN], cl[MAXN], cr[MAXN];
ll d, x[MAXN];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> tid >> tc;while (tc--) {cin >> n >> d;for (int i = 1; i <= n; ++i) cin >> x[i];for (int r = 2, l = 1; r <= n; ++r) {while (l <= r && x[r] - x[l] > d) ++l;prv[r] = l;}for (int l = n - 1, r = n; l; --l) {while (l <= r && x[r] - x[l] > d) --r;nxt[l] = r;}fill(buc, buc + n + 1, 0);++buc[nxt[1]];f[1] = 1;for (int i = 2, p = 1; i <= n; ++i) {while (p <= min(prv[i], i - 1)) --buc[nxt[p++]];f[i] = 1 + buc[i];if (prv[i] < i && nxt[prv[i]] == i) f[i] += f[prv[i]];cl[i] = buc[i + 1];++buc[nxt[i]];}fill(buc, buc + n + 1, 0);++buc[prv[n]];g[n] = 1;for (int i = n - 1, p = n; i; --i) {while (p >= max(nxt[i], i + 1)) --buc[prv[p--]];g[i] = 1 + buc[i];if (nxt[i] > i && prv[nxt[i]] == i) g[i] += g[nxt[i]];cr[i] = buc[i - 1];++buc[prv[i]];}ll ans = 0;for (int i = 2; i < n - 1; ++i) {int x = cl[i] + (prv[i] < i && nxt[prv[i]] == i + 1 ? f[prv[i]] : 0);int y = cr[i + 1] + (nxt[i + 1] > i + 1 && prv[nxt[i + 1]] == i ? g[nxt[i + 1]] : 0);ans += (ll)x * y;}cout << ans << '\n';}return 0;
}