以奶牛站立的围栏端点作为状态，用线段树区间赋值加单点查询求出正下方最近的围栏，自底向上 O(N log C) 递推最小水平距离。
OJ: roj
题目 ID: 3176
难度:提高
标签:动态规划线段树区间赋值坐标平移python
创建: 2026-10-01 23:10
更新: 2026-10-10 13:00
形式化题目
平面上有
一个点从起点出发，反复执行：
- 沿竖直方向下落，横坐标不变；
- 一旦落在某条围栏上，就沿这条围栏水平移动到它的左端点或右端点；
- 从端点继续下落，直到落在
的地面上，再沿地面走到原点。
竖直方向的距离不计。求水平方向走过的总距离的最小值。
正解
思路
第一步：竖直下落不花钱，状态只需要记录"站在哪条围栏的哪个端点上"。
奶牛在空中时不能横向移动，所以"在空中"这个瞬态没有选择余地，不必作为状态。真正要做决策的时刻，是它落到一条围栏之后的下一步：向左端走还是向右端走。而一条围栏
其中
第二步：写清转移，找出真正的瓶颈。
设
因为
第三步：瓶颈是查询
状态数已经被压到
注意
这正是"区间赋值 + 单点查询"，用线段树可以做到
区间只有
第四步：线段树上不写 pushdown。
本题的赋值是"整段覆盖"，而且赋值顺序就是层号递增，因此可以只在 (层号, 颜色)，查询时沿根到叶的路径取层号最大的那个标记：
- 修改：把
拆成 个整段节点，写入 (i, i)； - 查询
：从叶子走到根，取时间戳最大的节点；都没有则返回地面 。
父节点的标记时间一定不晚于子节点，所以"路径上时间戳最大者"就是最后一次覆盖。省掉 pushdown 后既不用递归，常数也小。
第五步：实现顺序不能颠倒。
对第
下面的表格用题面样例（
| 层号 | 区间 | 左端点下方 | 右端点下方 | ||
|---|---|---|---|---|---|
| 1 | 0 | 2 | 0 | 1 | |
| 2 | 1 | 3 | 0 | 2 | |
| 3 | 0 | 3 | 2 | 4 | |
| 4 | 3 | 4 | 2 | 3 |
读者应重点观察第 3、4 行：第 4 层的左端点
下面这张图展示样例中"落到哪条围栏 → 走到哪个端点"的两条候选路线，以及为什么最终答案是 4。
flowchart TD
start["起点 (0, 4)<br/>正下方 = 围栏 4"] --> l4["围栏 4 左端 (-2, 4)<br/>d = 4"]
start --> r4["围栏 4 右端 (1, 4)<br/>d = 3"]
l4 --> |"下落到围栏 3"| l3["围栏 3 左端 (-3, 3)<br/>再下落到地面"]
r4 --> |"下落到围栏 2"| r2["围栏 2 右端 (2, 2)<br/>再下落到地面"]
l3 --> ans["取较小值：4"]
r2 --> ans
两条路线分别对应 DP 表格里第 4 行的两个候选值
代码
代码就是上面五步的直译：query 是 assign 是"把本层刷上去"，ground_cost 是那个 endpoint_costs 按 fences[0] 是当作地面用的虚拟围栏。
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-10 13:00
* update_at: 2026-10-10 13:00
*/
// 围栏：线段树区间覆盖（记时间戳）+ 端点自底向上递推
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int ORIGIN = 100001; // 坐标整体平移量
const int SIZE = 1 << 18; // 线段树叶子数
const int GROUND = 0; // 地面编号
int stamp[SIZE * 2]; // 节点整段被覆盖的层号（越大表示覆盖越晚）
int who[SIZE * 2]; // 节点整段被哪条围栏覆盖，0 表示地面
int f_left[300005], f_right[300005]; // 围栏端点（编号即层号 y）
int down[300005][2]; // 每条围栏左右端点到地面的最少水平距离
// 把横坐标区间 [left,right] 整段覆盖成围栏 value
void assign_range(int left, int right, int value) {
left += SIZE;
right += SIZE + 1;
while (left < right) {
if (left & 1) {
stamp[left] = who[left] = value;
left++;
}
if (right & 1) {
right--;
stamp[right] = who[right] = value;
}
left >>= 1;
right >>= 1;
}
}
// 横坐标 x 正上方最近的一条围栏编号（没有围栏时是地面）
int query(int x) {
int node = x + SIZE;
int latest = 0, res = GROUND;
while (node) {
if (stamp[node] > latest) { // 越晚的覆盖越贴近上方
latest = stamp[node];
res = who[node];
}
node >>= 1;
}
return res;
}
// 从 (x, 某个高度) 竖直下落，再沿接住它的围栏走到端点下到地面
int ground_cost(int x) {
int below = query(x);
int a = f_left[below], b = f_right[below];
int da = (a > x ? a - x : x - a) + down[below][0];
int db = (b > x ? b - x : x - b) + down[below][1];
return da < db ? da : db;
}
int main() {
int n, s;
if (scanf("%d %d", &n, &s) != 2) {
return 0;
}
s += ORIGIN;
f_left[GROUND] = f_right[GROUND] = ORIGIN; // 地面：两端点都取原点
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d %d", &a, &b);
f_left[i] = a + ORIGIN;
f_right[i] = b + ORIGIN;
}
// 自底向上：查两端点脚下的围栏（此时树里只有更低的层），再把本层覆盖上去
for (int level = 1; level <= n; level++) {
down[level][0] = ground_cost(f_left[level]);
down[level][1] = ground_cost(f_right[level]);
assign_range(f_left[level], f_right[level], level);
}
printf("%d\n", ground_cost(s));
return 0;
}#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 23:35
# update_at: 2026-10-01 23:35
import sys
ORIGIN = 100_001 # 坐标整体平移量：原坐标 [-100000, 100000] 变成 [1, 200001]
SIZE = 1 << 18 # 线段树的叶子数，取 2 的幂且大于 200001
GROUND = 0 # 地面编号；它的两个端点都取原点，落在上面等于已经走出场地
STAMP: list[int] = [0] * (SIZE * 2) # 节点整段被覆盖的层号；层号越大表示覆盖越晚
WHO: list[int] = [0] * (SIZE * 2) # 节点整段被哪条围栏覆盖，0 表示地面
def assign(left: int, right: int, value: int) -> None:
"""把横坐标区间 [left, right] 整段覆盖成围栏 value。
只写在能拼出这个区间的 O(log SIZE) 个节点上，不往叶子推；覆盖时间直接用层号
value（层号随处理顺序递增），点查询时沿根到叶取时间戳最大的节点就是最后一次覆盖。
"""
left += SIZE
right += SIZE + 1
while left < right:
if left & 1:
STAMP[left], WHO[left] = value, value
left += 1
if right & 1:
right -= 1
STAMP[right], WHO[right] = value, value
left >>= 1
right >>= 1
def query(x: int) -> int:
"""横坐标 x 正上方最近的一条围栏编号（它上方没有围栏时是地面 GROUND）。"""
node = x + SIZE
latest, who = 0, GROUND
while node:
if STAMP[node] > latest: # 越晚的覆盖越贴近上方，会遮住更早的覆盖
latest, who = STAMP[node], WHO[node]
node >>= 1
return who
def ground_cost(fences: list[tuple[int, int]], down: list[tuple[int, int]], x: int) -> int:
"""从 (x, 某个高度) 竖直下落，再沿着接住它的那条围栏走到端点下到地面。
自由下落途中不做水平移动，所以接住奶牛的那条围栏是唯一的；站上去以后，
最优走法只取决于站在哪个端点，于是取"走左端点"和"走右端点"的较小值。
"""
below = query(x)
(left, right), (dl, dr) = fences[below], down[below]
return min(abs(left - x) + dl, abs(right - x) + dr)
def endpoint_costs(fences: list[tuple[int, int]]) -> list[tuple[int, int]]:
"""自底向上算出每条围栏左右端点到地面所需的最少水平距离。
第 0 项是当作地面用的虚拟围栏，两个端点都在原点，所以距离是 (0, 0)。
每层先查两端点脚下的围栏（此时树里只有更低的层），再把本层覆盖上去——
顺序颠倒会让端点查到自己。
"""
down: list[tuple[int, int]] = [(0, 0)] * len(fences)
for level in range(1, len(fences)):
left, right = fences[level]
down[level] = (ground_cost(fences, down, left), ground_cost(fences, down, right))
assign(left, right, level)
return down
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, s = next(data), next(data) + ORIGIN
# 围栏编号就是层号 y；GROUND 代表地面，它的端点取原点，落到它上面等于已经出场地
fences: list[tuple[int, int]] = [(ORIGIN, ORIGIN)] + [
(next(data) + ORIGIN, next(data) + ORIGIN) for _ in range(n)
]
print(ground_cost(fences, endpoint_costs(fences), s))
if __name__ == "__main__":
solve()复杂度
- 时间复杂度：每条围栏做 2 次单点查询和 1 次区间赋值，最后再做 1 次查询，每次
；读入 。总时间复杂度 ，其中 。 时约 次基本操作，实测单测例约 秒。 - 空间复杂度：线段树的两个标记数组（
STAMP、WHO）各项，加上围栏端点数组和 DP 数组各 ，总空间 ，实测峰值约 34 MB，低于 128 MB 限制。
总结
本题的难点不在 DP 方程本身，而在"谁挡住了下落路径"这个几何查询。把状态从"围栏上的任意点"压缩到"两个端点"之后，递推式就只剩下