题解

思路

对固定询问 $(x,y)$，若当前已经能够到达的最高位置为 $h$，那么区间 $[x,h]$ 上每个高度都可通过向下移动到达。于是，所有满足 $x\le l_i\le h$ 且 $r_i\le y$ 的绳索都可以使用。不断用这些绳索扩张 $h$，直到不再变化，即得到答案。

做法

子任务 1 可对每次询问反复扫描全部绳索。每当 $h$ 增大后重新扫描，直到达到不动点。其时间复杂度为 $O(qm^2)$。

子任务 2 可以把询问按上界 $y$ 离线。令 $a_x$ 表示只允许使用上端不超过当前扫描高度的绳索时，从 $x$ 出发可到达的最高位置。初始 $a_x=x$。当扫描到唯一一根上端为 $r$、下端为 $l$ 的绳索时，恰好需要对所有 $x\le l$ 且 $a_x\ge l$ 的位置执行 $a_x\gets r$。直接扫描 $[1,l]$ 即可，总复杂度 $O(nm+q)$。

满分做法仍按 $y$ 从小到大扫描，但用线段树维护数组 $a$。线段树结点记录区间最大值和严格次大值。对于一次修改，在目标前缀中：若最大值小于 $l$，整段没有位置需要修改；若严格次大值小于 $l$，只有所有最大值位置满足条件，可以把这些最大值整体改为 $r$；否则递归到两个儿子。询问是单点查询。

正确性来自离线不变量：处理完所有上端不超过 $y$ 的绳索后，$a_x$ 等于询问 $(x,y)$ 的答案。加入绳索 $(l,r)$ 时，从 $x$ 能使用它当且仅当 $x\le l$ 且此前 $a_x\ge l$；而 $r$ 是当前新出现的最大上端，所以使用后答案恰为 $r$。线段树修改与这一条件逐点完全等价，因此归纳成立。

复杂度

复杂度方面，每次递归到不能整段处理的位置时，会合并至少两个不同的区间最大值；可用不同值块的数量作为势能。所有修改总计 $O((n+m)\log n)$，所有单点查询总计 $O(q\log n)$，空间复杂度 $O(n+q)$。