题目描述

农夫约翰为他的奶牛们建造了一个围栏障碍训练场，以供奶牛们玩耍。

训练场由 $N$ 个不同长度的围栏组成，每个围栏都与 $x$ 轴平行，并且第 $i$ 个围栏的 $y$ 坐标为 $i$。

训练场的出口位于原点，起点位于 $(S, N)$

这些牛会从起点处开始向下走，当它们碰到围栏时会选择沿着围栏向左或向右走，走到围栏端点时继续往下走，按照此种走法一直走到出口为止。

请问，这些牛从开始到结束，行走的水平距离最少为多少。

输入格式

第一行包含两个整数 $N$ 和 $S$。

第 $2..N+1$ 行，每行包含两个整数 $A_i, B_i$，表示一个围栏的起始横坐标和结束横坐标，其中第 $i+1$ 行表示第 $i$ 个围栏的数据。

起点坐标满足 $A_N \le S \le B_N$。

输出格式

输出一个整数，表示最小水平行走距离。

样例

4 0 
-2 1
-1 2
-3 0
-2 1

4

样例解释

输入

$N = 4, S = 0$ 围栏（从下往上编号 1 到 4）： 1: $A_1 = -2, B_1 = 1$ 2: $A_2 = -1, B_2 = 2$ 3: $A_3 = -3, B_3 = 0$ 4: $A_4 = -2, B_4 = 1$

起点在 $(0, 4)$，即第 4 层横坐标 0 处。

行走过程

牛从 $(0,4)$ 垂直向下走，碰到第 4 层围栏（$y=4$，横坐标范围 $[-2,1]$），因为起点横坐标 0 在围栏内，所以牛必须选择向左或向右走到围栏端点，然后垂直向下。

我们需要计算所有可能路径中的最小水平距离。

计算

可以采用动态规划从下往上计算。

定义 $dp[i][0]$ 表示到达第 $i$ 层围栏左端点 $A_i$ 时的最小总水平距离，$dp[i][1]$ 表示到达第 $i$ 层围栏右端点 $B_i$ 时的最小总水平距离。

从第 $i$ 层到第 $i-1$ 层的转移：

• 如果从第 $i$ 层左端点 $A_i$ 垂直向下，会落到第 $i-1$ 层横坐标 $A_i$ 处，如果 $A_i$ 在第 $i-1$ 层围栏内部（$A_{i-1} \le A_i \le B_{i-1}$），则牛必须走到第 $i-1$ 层的左端点或右端点。否则，如果 $A_i$ 在围栏左边（$A_i < A_{i-1}$），则直接落在第 $i-1$ 层左端点；如果 $A_i$ 在围栏右边（$A_i > B_{i-1}$），则直接落在第 $i-1$ 层右端点。
• 类似地处理从第 $i$ 层右端点 $B_i$ 垂直向下的情况。

具体转移公式较复杂，需要分类讨论。

另一种思路：从下往上考虑，用两个变量 $L$ 和 $R$ 表示当前层（第 $i$ 层）围栏的左端点和右端点对应的最小水平距离。

但更常见的方法是从上往下动态规划，但由于牛是从上往下走，我们需要知道从起点到每个围栏端点的最小水平距离。

样例计算

我们手动计算样例。

围栏从上到下（$i=4$ 到 $i=1$）：

• 第 4 层：$[-2,1]$，起点 $x=0$ 在内部，所以牛必须向左走到 -2 或向右走到 1。 从起点到左端点水平距离 = $|0 - (-2)| = 2$ 到右端点水平距离 = $|0 - 1| = 1$ 所以 $dp[4][0] = 2, dp[4][1] = 1$

• 第 3 层：$[-3,0]$ 从第 4 层左端点 $x=-2$ 垂直向下落到 $x=-2$，检查是否在第 3 层围栏内：$[-3,0]$ 包含 -2，所以需要走到左端点或右端点。

  • 走到左端点 $-3$：水平距离增加 $| -2 - (-3) | = 1$，总距离 $dp[4][0] + 1 = 2+1=3$。
  • 走到右端点 $0$：水平距离增加 $| -2 - 0 | = 2$，总距离 $2+2=4$。 从第 4 层右端点 $x=1$ 垂直向下落到 $x=1$，$1 > 0$，超出围栏右端点，所以直接落到第 3 层右端点 $x=0$，水平距离增加 $|1-0|=1$，总距离 $dp[4][1] + 1 = 1+1=2$（注意：从 $x=1$ 落到 $x=0$ 是因为围栏右端点是 0，牛必须走到端点才能向下？实际上，如果落点超出围栏，牛会直接落到最近的端点，然后垂直向下？题目描述：“当它们碰到围栏时会选择沿着围栏向左或向右走，走到围栏端点时继续往下走”。所以如果垂直下落时没有碰到围栏（即落点不在围栏上），则直接继续下落；如果落点在围栏上，则必须沿围栏走到端点再下落。

  因此，对于第 4 层右端点 $x=1$ 垂直下落，落点 $x=1$ 不在第 3 层围栏 $[-3,0]$ 内，所以直接继续下落（即落到第 2 层？不对，下落过程会依次经过每一层。当从第 4 层端点下落时，首先到达第 3 层高度 $y=3$，如果 $x=1$ 不在第 3 层围栏上，则继续下落至第 2 层，直到碰到某个围栏或地面。所以我们需要考虑从当前端点下落，会落到下面的哪个围栏。

因此，我们需要知道从某个点垂直下落，会碰到下面哪一层的围栏（如果碰到）。这可以通过预处理每个围栏的覆盖区间，然后对于每个端点，找到下面第一个包含该 $x$ 坐标的围栏。

由于 $N$ 较大（30000），需要高效算法。

更高效的算法：线段树优化 DP

一种经典做法是使用动态规划结合线段树或平衡树优化。

定义 $dp[i][0]$ 和 $dp[i][1]$ 如上。

转移时，对于第 $i$ 层的左端点 $A_i$，我们需要知道从 $(A_i, i)$ 垂直下落会落到哪里。设下落过程中碰到的下一个围栏是 $j$（$j < i$），且 $A_i$ 在围栏 $j$ 的内部（$A_j \le A_i \le B_j$），那么牛必须从 $A_i$ 走到 $A_j$ 或 $B_j$。因此：

$$dp[i][0] = \min( dp[j][0] + |A_i - A_j|, dp[j][1] + |A_i - B_j| )$$

其中 $j$ 是下面第一个满足 $A_j \le A_i \le B_j$ 的围栏。如果不存在这样的 $j$，则牛会直接落到地面（原点），此时水平距离为 $|A_i - 0| = |A_i|$。

类似地，对于右端点 $B_i$：

$$dp[i][1] = \min( dp[j][0] + |B_i - A_j|, dp[j][1] + |B_i - B_j| )$$

因此，我们需要快速找到每个端点垂直下落碰到的下一个围栏。这可以通过从下往上扫描，用线段树维护当前每个坐标点被哪个围栏覆盖。

具体步骤：

1. 将围栏按 $y$ 坐标（即层数 $i$）从小到大排序（输入已经按层给出，第 $i$ 行就是第 $i$ 层）。
2. 从下往上处理（$i$ 从 $1$ 到 $N$），用线段树维护区间 $[A_i, B_i]$ 被第 $i$ 层覆盖。对于端点 $A_i$ 和 $B_i$，查询 $x=A_i$ 和 $x=B_i$ 处当前被哪个围栏覆盖（即下面最近的围栏）。由于我们从下往上处理，查询时得到的是已经处理过的下面某层围栏 $j$（$j < i$）。
3. 然后计算 $dp[i][0]$ 和 $dp[i][1]$。
4. 最后，对于起点 $(S, N)$，我们需要找到从 $S$ 下落碰到的第一个围栏（应该是第 $N$ 层本身，因为起点在第 $N$ 层上？实际上起点在第 $N$ 层围栏上，所以牛一开始就在围栏上，必须走到左端点或右端点。因此，最小水平距离为 $\min(dp[N][0] + |S - A_N|, dp[N][1] + |S - B_N|)$。

样例验证

我们按照此方法计算样例。

围栏（层数从 1 到 4）： 1: $[-2,1]$ 2: $[-1,2]$ 3: $[-3,0]$ 4: $[-2,1]$

从下往上处理：

第 1 层：$A_1=-2, B_1=1$ 下面没有围栏（地面），所以 $dp[1][0] = | -2 - 0 | = 2$，$dp[1][1] = | 1 - 0 | = 1$。

第 2 层：$A_2=-1, B_2=2$ 查询 $x=-1$：当前线段树中 $x=-1$ 被第 1 层覆盖（因为第 1 层 $[-2,1]$ 包含 -1），所以 $j=1$。 $dp[2][0] = \min( dp[1][0] + | -1 - (-2) |, dp[1][1] + | -1 - 1 | ) = \min(2+1, 1+2) = \min(3,3) = 3$ 查询 $x=2$：$x=2$ 不在第 1 层围栏内（第 1 层 $[-2,1]$），所以下面没有围栏，直接到地面： $dp[2][1] = |2-0| = 2$

第 3 层：$A_3=-3, B_3=0$ 查询 $x=-3$：不在第 2 层和第 1 层内，所以直接到地面：$dp[3][0] = | -3 | = 3$ 查询 $x=0$：在第 1 层内（$[-2,1]$ 包含 0），$j=1$： $dp[3][1] = \min( dp[1][0] + |0 - (-2)|, dp[1][1] + |0 - 1| ) = \min(2+2, 1+1) = \min(4,2) = 2$

第 4 层：$A_4=-2, B_4=1$ 查询 $x=-2$：在第 3 层内？第 3 层 $[-3,0]$ 包含 -2，所以 $j=3$： $dp[4][0] = \min( dp[3][0] + | -2 - (-3) |, dp[3][1] + | -2 - 0 | ) = \min(3+1, 2+2) = \min(4,4) = 4$ 查询 $x=1$：在第 2 层内？第 2 层 $[-1,2]$ 包含 1，所以 $j=2$： $dp[4][1] = \min( dp[2][0] + |1 - (-1)|, dp[2][1] + |1 - 2| ) = \min(3+2, 2+1) = \min(5,3) = 3$

起点 $S=0$ 在第 4 层上： 最小水平距离 = $\min( dp[4][0] + |0 - (-2)|, dp[4][1] + |0 - 1| ) = \min(4+2, 3+1) = \min(6,4) = 4$

输出 4，与样例一致。

数据范围

• $1 \le N \le 30000$
• $-10^5 \le S \le 10^5$
• $-10^5 \le A_i, B_i \le 10^5$

算法总结

1. 读入 $N, S$ 和围栏数据。
2. 将坐标离散化（因为 $A_i, B_i$ 范围较大但 $N$ 较小，最多 $2N$ 个端点）。
3. 从下往上（$i$ 从 $1$ 到 $N$）处理围栏：
   • 对于端点 $A_i$ 和 $B_i$，在线段树上查询该 $x$ 坐标当前被哪个围栏覆盖（即下面最近的围栏 $j$）。
   • 计算 $dp[i][0]$ 和 $dp[i][1]$。
   • 将区间 $[A_i, B_i]$ 在线段树上标记为被第 $i$ 层覆盖（覆盖信息可以记录层号 $i$）。
4. 最后计算起点 $S$ 的最小水平距离：找到 $S$ 垂直下落碰到的第一个围栏（即第 $N$ 层），然后按公式计算。
5. 输出结果。

线段树设计

线段树需要支持：

• 区间赋值：将区间 $[l, r]$ 覆盖为层号 $i$。
• 单点查询：查询某个 $x$ 坐标当前被哪个层覆盖。

由于是区间赋值，可以用懒标记线段树。

复杂度

• 离散化 $O(N \log N)$
• 线段树操作 $O(N \log N)$
• 总复杂度 $O(N \log N)$，可以处理 $N=30000$。

注意事项

• 起点 $S$ 可能不在任何围栏上？题目保证 $A_N \le S \le B_N$，所以起点在第 $N$ 层围栏上。
• 地面视为原点 $(0,0)$，如果垂直下落没有碰到任何围栏，则水平距离就是 $|x|$。
• 注意坐标可能为负，离散化时需注意。