P17833 [CSP-S 2026] 迁徙 / migrate

数轴上有 \(n\) 个点 \(x_1\sim x_n\)。给定 \(d\)，若 \(|x_i-x_j|\le d\) 则连边 \(i\leftrightarrow j\)。

对 \(1 \le u，称点对 \((u,v)\) 是双径的，当且仅当 \(u \leadsto v\) 恰有两条最短路径。求出双径点对数目。

\(\sum n \le 2\times 10^6\)，\(d \le 2 \times 10^{18}\)，1 秒，1024 MB。

双指针求出 \(i\) 左右可达的最远点 \(l_i,r_i\)，则 \(i\) 的出边是 \([l_i,r_i]\)。

从 \(u\) 开始不断跳 \(r_i\) 链得到路径 \(u \to a_1 \to a_2\to\cdots \to a_m\)，其中 \(a_m \ge v\) 是首个越过 \(v\) 的点，显然这是最短路。

反过来从 \(v\) 开始跳 \(l_i\) 链得到路径 \(b_0\gets b_1\gets\cdots\gets b_{m-1} \gets v\)，其中 \(b_0 \le u\) 是首个越过 \(u\) 的点。

不妨设 \(a_0=u\) 且 \(b_m=v\)，我们使用 \(a_0 \sim a_m\) 和 \(b_0 \sim b_m\) 刻画双径条件。

性质 1 \(\forall i, a_i-b_i \le 1\)。

证明 若 \((a_i,b_i)\) 中间存在中转点 \(x\)，取路径 \(u \leadsto a_{i-1} \to x \to b_{i+1} \leadsto v\) 得到第三条最短路。

性质 2 \(a_i-b_i=1\) 的 \(i\) 有且仅有一个，其余位置均满足 \(a_i=b_i\)。

证明 路径 \(u \leadsto a_i \leadsto v\) 和 \(u \leadsto b_i \leadsto v\) 均得到最短路，每个分界点产生 \(2\) 个分支，故恰有 \(1\) 个分界点。

枚举并钦定 \(a_i=x+1\) 且 \(b_i=x\)，其中 \(x \in [2,n-2]\)，对跨越 \(x\) 的 \((u,v)\) 计数。注意 \(x\) 两侧 \(l_i\) 链和 \(r_i\) 链完全重合。

对两侧独立计数。设 \(f_i\) 表示满足下述条件的起点 \(u\) 数目：

  • \(u \to r_u \to r_{r_u}\to \cdots\) 以 \(i\) 结尾。
  • \(u \leadsto i\) 的最短路唯一。

分讨路径的最后一步进行转移：

  • 起点为 \(i\)，贡献 \(1\)。
  • 起点 \(j \in (l_i,i)\)，若 \(r_j=i\) 则 \(j \leadsto i\) 贡献 \(1\)。
  • 路径先到达 \(l_i\) 再从 \(l_i\) 跳到 \(i\)，要求 \(r_{l_i}=i\)，贡献 \(f_{l_i}\)。

递推式

\[f_i=1+\sum_{j \in (l_i,i)} [r_j=i]+[l_i

同理定义 \(g_i\) 表示只跳 \(l_i\) 链唯一可达 \(i\) 的终点数目，递推

\[g_i=1+\sum_{j \in (i,r_i)} [l_j=i]+[r_i>i \land l_{r_i}=i] g_{r_i} \]

固定 \(b_i=x,a_i=x+1\)，分析左侧起点的方案数：

  • 起点 \(j \in (l_x,x)\) 一步跳到 \(a_i\)，要求 \(r_j=x+1\)，贡献 \(1\)。
  • 起点沿唯一路径跳到 \(l_x\) 再跳到 \(a_i\)，要求 \(r_{l_x}=x+1\)，贡献 \(f_{l_x}\)。

同理两侧可选数目为

\[\begin{aligned} L&=\sum_{j \in (l_x,x)} [r_j=x+1] +[l_xx+1 \land l_{r_{x+1}}=x] g_{r_{x+1}} \end{aligned} \]

容易做到 \(O(n^2)\)。我们只要在区间中查询某数出现次数，二分可以简单优化到小常数 \(O(n \log n)\) 通过。

const int N = 2e6 + 5;
int n, l[N], r[N];
i64 d, a[N], f[N], g[N];
vector p[N], q[N];void _main() {cin >> n >> d;for (int i = 1; i <= n; i++) p[i].clear(), q[i].clear();for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1, j = 1; i <= n; i++) {while (j < n && a[j+1] - a[i] <= d) j++;r[i] = j, p[j].pb(i);}for (int i = n, j = n; i >= 1; i--) {while (j > 1 && a[i] - a[j-1] <= d) j--;l[i] = j, q[j].pb(i);}for (int i = 1; i <= n; i++) reverse(all(q[i]));fill(f + 1, f + n + 1, 1), fill(g + 1, g + n + 1, 1);auto ask = [&](auto&& p, int l, int r, int x) -> int {if (l > r) return 0;return upper_bound(all(p[x]), r) - lower_bound(all(p[x]), l);};for (int i = 1; i <= n; i++) {if (l[i] < i && r[l[i]] == i) f[i] += f[l[i]];f[i] += ask(p, l[i]+1, i-1, i);}for (int i = n; i >= 1; i--) {if (r[i] > i && l[r[i]] == i) g[i] += g[r[i]];g[i] += ask(q, i+1, r[i]-1, i);}i64 res = 0;for (int x = 2; x <= n-2; x++) {i64 a = 0, b = 0;if (l[x] < x && r[l[x]] == x+1) a += f[l[x]];if (r[x+1] > x+1 && l[r[x+1]] == x) b += g[r[x+1]];a += ask(p, l[x]+1, x-1, x+1);b += ask(q, x+1, r[x+1]-1, x);res += a * b;}cout << res << '\n';
}