题目理解

我们有 $n$ 个区间 $[l_i, r_i]$，定义从区间 $x$ 可以跳到区间 $y$ 的条件是：

[ r_x \in [l_y, r_y] ]

即当前区间的右端点必须落在目标区间的范围内。

给定 $q$ 次询问，每次给出起点区间编号 $s$ 和终点区间编号 $t$，要求输出从 $s$ 到 $t$ 的最少跳跃次数，若无法到达则输出 impossible。

关键观察

1. 图论建模
   可以将每个区间看作图中的一个节点，如果 $r_x \in [l_y, r_y]$，则建立一条从 $x$ 到 $y$ 的有向边。那么问题转化为在有向图上求 $s$ 到 $t$ 的最短路径（边权为 1）。

2. 直接建图的复杂度问题
   $n$ 最大可达 $10^5$，如果直接枚举所有 $O(n^2)$ 的边对会超时。因此必须优化建图。

3. 贪心跳跃策略
   假设当前在区间 $x$，右端点为 $r_x$。在所有能跳到的区间中（即 $l_y \le r_x \le r_y$），选择 右端点 $r_y$ 最大 的区间跳，可以覆盖更远的距离，从而减少跳跃次数。
   这种贪心类似于在一条数轴上，每次选择能覆盖当前位置且延伸最远的区间。

4. 跳跃的单调性
   在贪心策略下，跳跃序列的右端点是单调不减的（实际上严格递增，除非出现相同右端点）。因此，如果 $r_s > r_t$，则一定不可能从 $s$ 到达 $t$（因为右端点只会增加或不变，但这里不变的情况很少，因为要跳到不同的区间）。

解题思路

1. 预处理“下一个”跳跃

对每个区间 $i$，我们想快速知道：从它出发，按照贪心策略（右端点最大）能跳到的下一个区间是哪个。

具体做法：

• 将区间按左端点 $l$ 排序（左端点相同则按右端点从大到小）。
• 用数据结构（如线段树或 ST 表）维护区间右端点的最大值，对于给定的 $r_x$，在所有满足 $l_y \le r_x$ 的区间中，找到 $r_y$ 最大的区间 $y$（且 $y \neq x$，除非允许自环，但这里通常不允许）。

这样我们可以为每个区间 $i$ 预先计算出 next[i]，表示从 $i$ 出发贪心一跳能到达的区间。

2. 倍增优化查询

由于 $n$ 和跳跃次数可能很大，我们使用 倍增法（Binary Lifting）来快速模拟多次跳跃。

定义：

• jump[i][k] 表示从区间 $i$ 出发，贪心跳 $2^k$ 步后到达的区间。
• 初始 jump[i][0] = next[i]。
• 转移：jump[i][k] = jump[ jump[i][k-1] ][k-1]。

3. 处理询问

对于询问 $(s, t)$：

1. 如果 $s = t$，答案是 $0$。
2. 如果 $r_s > r_t$，输出 impossible（因为右端点不会减少）。
3. 否则，先从 $s$ 贪心跳若干步，使得跳完后的区间 $p$ 满足 $r_p \ge r_t$，并且步数尽量少。
   • 具体方法：从高到低尝试倍增的幂 $k$，如果 jump[s][k] 的右端点仍小于 $r_t$，就跳这 $2^k$ 步。
4. 此时再判断：
   • 如果 $p = t$ 或者从 $p$ 可以直接一步跳到 $t$（即 $r_p \in [l_t, r_t]$），则得到总步数。
   • 否则可能需要再多跳一步：因为贪心路径可能跳过 $t$，所以先跳到 $p$，再检查 next[p] 是否能到 $t$。

复杂度分析

• 排序：$O(n \log n)$
• 预处理每个区间的 next[i]：$O(n \log n)$
• 倍增预处理：$O(n \log n)$
• 每个询问：$O(\log n)$

总复杂度：$O((n+q) \log n)$，可以处理 $n, q \le 10^5$ 的数据。

总结

这道题的核心是将区间跳跃问题转化为图的最短路问题，并利用 贪心选择右端点最大 的区间来减少边数，再通过 倍增法 快速模拟多次跳跃，从而高效回答询问。
关键点在于理解跳跃的单调性和贪心最优性，并熟练运用数据结构与倍增技巧。