题解：P17139 [KOI 2026 #1] 跳跃
lailai0916
·
·
题解
题意简述
第 i 个踏板位于 (X_i,i)。只能跳向编号更大的踏板，且一次跳跃要求横坐标差的绝对值不超过 D。求从每个踏板出发能够到达多少个踏板，包括起点本身。
解题思路
由于编号只能增大，所有可达关系都指向后缀。倒序处理踏板时，后继踏板的答案已经求出。
对起点 i，按照横坐标与 X_i 的关系，把可达踏板分为三个互不相交的集合：
先研究 R_i。若 R_i 非空，令 k 为其中编号最小的踏板。考虑一条从 i 到 k 的路径。因为 k 是路径上第一个横坐标大于 X_i 的踏板，其前驱 u 满足 X_u\le X_i。由 u 能跳到 k 可得：
X_k-X_i\le X_k-X_u\le D
所以 i 可以直接跳到 k。
此时 R_i 可以精确拆分为：
R_i=R_k\mathbin{\cup}\{j\mid i<j,X_i<X_j\le X_k\}
右侧第二部分中的踏板都能由 i 直接到达。对于 R_k 中的踏板，可以先从 i 到 k，再沿原路径到达。故右侧包含于 R_i。
反过来，任取 j\in R_i。若 X_j\le X_k，它属于第二部分。若 X_j>X_k，在一条从 i 到 j 的路径上，取第一个横坐标大于 X_k 的踏板 v，并记其前驱为 u。此时 X_u\le X_k<X_v，所以：
X_v-X_k\le X_v-X_u\le D
对左侧完全对称。若 $k$ 是 $L_i$ 中编号最小的踏板，则：
$$
L_i=L_k\mathbin{\cup}\{j\mid i<j,X_k\le X_j<X_i\}
$$
横坐标等于 $X_i$ 的任意后续踏板都能由 $i$ 一步到达。因此，$E_i$ 恰好由 $i$ 与后缀中所有坐标等于 $X_i$ 的踏板组成。
倒序枚举 $i$，并维护已经加入的后缀。为了使用上述递推，需要支持两种区间查询：
1. 查询某个横坐标区间内的最小踏板编号，用于找到 $L_i$ 或 $R_i$ 中的 $k$；
2. 查询区间内已经加入的踏板数量，用于统计递推中新增加且能够直接跳到的部分。
先将全部横坐标离散化。用迭代线段树维护每个坐标区间中的最小编号，用树状数组维护数量前缀和。处理 $i$ 时，后缀 $i+1,\dots,N$ 已全部加入。
对右侧，在线段树中查询坐标区间 $(X_i,X_i+D]$ 的最小编号 $k$。若存在，就继承 $|R_k|$，再用树状数组统计 $(X_i,X_k]$ 内的后缀踏板数量。左侧使用区间 $[X_i-D,X_i)$ 寻找 $k$，并统计 $[X_k,X_i)$。等坐标部分可以直接查询坐标 $X_i$ 的已有数量并加一。
每个踏板只进行常数次区间查询和一次插入。时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。
## 正确性证明
对每个 $i$，上述论证证明了 $R_i$ 与 $L_i$ 的递推等式。两个等式中的继承集合和直接跳跃集合横坐标范围不交，因此计数不会重复。$E_i$ 中的踏板与 $i$ 横坐标相同，且编号更大时一定能一步到达；可达路径又不能返回更小编号，所以后缀等坐标计数恰好等于 $|E_i|$。
倒序处理保证递推依赖的 $|L_k|$ 与 $|R_k|$ 已经求出。线段树返回指定范围内编号最小的后缀踏板，正好对应递推定义的 $k$；树状数组则准确统计直接跳跃集合的大小。因此算法分别得到三个集合的真实大小。
三个集合按照横坐标与 $X_i$ 的大小关系划分全部可达踏板，彼此不交且没有遗漏。将它们的大小相加，所得就是每个起点的可达踏板总数。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=300005;
const int M=1048576;
const int inf=0x3f3f3f3f;
int n,d,m,s;
int x[N],v[N],bit[N],tr[M];
int lt[N],rt[N],ans[N];
void add(int x,int val)
{
for(int i=x;i<=m;i+=i&-i)bit[i]++;
x+=s-1;
tr[x]=val;
while(x>1)
{
x>>=1;
tr[x]=min(tr[x<<1],tr[x<<1|1]);
}
}
int ask_sum(int x)
{
int res=0;
for(int i=x;i;i-=i&-i)res+=bit[i];
return res;
}
int ask_min(int l,int r)
{
l+=s-1;
r+=s-1;
int res=inf;
while(l<=r)
{
if(l&1)res=min(res,tr[l++]);
if(!(r&1))res=min(res,tr[r--]);
l>>=1;
r>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>d;
for(int i=1;i<=n;i++)
{
cin>>x[i];
v[i]=x[i];
}
sort(v+1,v+n+1);
m=unique(v+1,v+n+1)-v-1;
s=1;
while(s<m)s<<=1;
fill(tr,tr+s*2,inf);
for(int i=n;i>=1;i--)
{
int p=lower_bound(v+1,v+m+1,x[i])-v;
ans[i]=ask_sum(p)-ask_sum(p-1)+1;
int l=upper_bound(v+1,v+m+1,x[i])-v;
int r=upper_bound(v+1,v+m+1,x[i]+d)-v-1;
if(l<=r)
{
int k=ask_min(l,r);
if(k!=inf)
{
int q=lower_bound(v+1,v+m+1,x[k])-v;
rt[i]=rt[k]+ask_sum(q)-ask_sum(l-1);
ans[i]+=rt[i];
}
}
l=lower_bound(v+1,v+m+1,x[i]-d)-v;
r=lower_bound(v+1,v+m+1,x[i])-v-1;
if(l<=r)
{
int k=ask_min(l,r);
if(k!=inf)
{
int q=lower_bound(v+1,v+m+1,x[k])-v;
lt[i]=lt[k]+ask_sum(r)-ask_sum(q-1);
ans[i]+=lt[i];
}
}
add(p,i);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<(i==n?'\n':' ');
return 0;
}
```