P14208 [ROI 2016 Day1] 人烟之山

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day1 T4.** ***[Обитаемые горы](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day1.pdf)*** 改编自 Arkadi Strugatsky 与 Boris Strugatsky 的科幻中篇《人烟之岛》。

不知名之父国的政$ $府计划在与洪提亚接壤的多山地区修建一座反弹道防御塔。 该地区的一段山脉以一条折线表示，这条折线由 $n$ 个线段组成，依次连接 $n + 1$ 个顶点，这些顶点按 $x$ 坐标递增排列。顶点编号为 $0$ 到 $n$，线段编号为 $1$ 到 $n$，其中第 $i$ 个线段连接编号为 $i - 1$ 与 $i$ 的两个顶点。 顶点编号 $0$ 位于点 $(0, 0)$。第 $i$ 个线段由其在水平轴上的投影长度 $d_i$ 与斜率 $k_i$ 给出。于是，若编号为 $i - 1$ 的顶点坐标为 $(x_{i-1}, y_{i-1})$，则第 $i$ 个顶点的坐标可按如下计算：$(x_{i-1} + d_i, y_{i-1} + k_i \cdot d_i)$。最后一个顶点的 $y$ 坐标为 $0$，即 $y_n = 0$。 :::align{center}  ::: 若点 $A$ $(x_A, y_A)$ 到点 $B$ $(x_B, y_B)$ 的线段上**没有任何一点**位于折线**下方**（严格意义上），则称点 $A$ 从点 $B$ 是**直线可见**的。 塔是一条垂直的非零长度线段，其下端点位于折线上。若塔的上端点处于某位公民的直线可见范围内，则该公民感到安全。 设塔的上端点在 $(x, y)$。考虑两名侦察兵，他们从塔的下端点分别向西（$x$ 坐标减小方向）与向东（$x$ 坐标增大方向）出发。每名侦察兵沿着山脉表面奔跑，直到进一步移动会使塔的上端点离开其直线可见范围，或直到到达山脉的边界为止。 政$ $府准备了 $m$ 种塔的位置方案，每个方案由两个整数 $(u_j, v_j)$ 表示——即塔的上端点坐标。要求编写程序，对每个方案分别确定两名侦察兵能跑到的点的 $x$ 坐标。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 400\,000$）——折线的线段数量以及塔的位置方案数量。 随后的输入约束取决于常数 $C$ 的取值，$C$ 可为 $10^4$ 或 $10^9$，具体由子任务决定（见评分表）。 接下来的 $n$ 行中，每行包含两个整数 $d_i, k_i$（$1 \le d_i \le C$；$-C \le k_i \le C$）——第 $i$ 个线段在水平轴上的投影长度与斜率（$0 = x_0 < x_1 < \cdots < x_i < \cdots < x_n \leq C$；$y_0 = y_n = 0$；$-C \le y_i \le C$）。 接下来的 $m$ 行中，每行包含两个整数 $u_j, v_j$（$0 \leq u_j \leq C$，$-C \leq v_j \leq C$）——第 $j$ 个方案中塔的上端点坐标。

输出共 $m$ 行，每行包含两个整数 $l_j$ 与 $r_j$——分别为第 $j$ 个方案中向西和向东奔跑的侦察兵能到达的点的 $x$ 坐标。保证 $l_j$ 与 $r_j$ 都为整数。

### 样例解释 :::align{center}  样例 1 示意 ::: 请注意，根据题目中的定义，线段 $(6, 2)$ 与 $(7, 1)$ 之间的所有点均处于塔的上端点的直线可见范围内。 :::align{center}  样例 2 示意 ::: 在该测试中，所有方案的塔的下端点都位于同一点。 :::align{center}  样例 3 示意 ::: 在该测试中，所有方案的塔的上端点都位于同一条水平直线上。请注意，塔的下端点可以位于山脉链的端点处。 :::align{center}  样例 4 示意 ::: 在第四个测试中说明，在不知名之父国，整条山脉链可能完全位于其两端点的高度之下。 ### 数据范围 | 子任务编号 | 分值 | $n, m$ | $C$ | 其他限制 | 必须通过的子任务 | |:--:|:--:|:--:|:--:|:--:|:--:| | 1 | 9 | $1 \le n, m \le 100$ | $C = 10^4$ | $k_i = \pm 1$ | | | 2 | 9 | $1 \le n, m \le 100$ | $C = 10^4$ | | 1 | | 3 | 10 | $1 \le n, m \le 3000$ | $C = 10^9$ | | 1, 2 | | 4 | 11 | $1 \le n, m \le 100\,000$ | $C = 10^9$ | $k_i = \pm 1$ | 1 | | 5 | 11 | $1 \le n, m \le 100\,000$ | $C = 10^9$ | 所有塔的下端点重合 | | | 6 | 12 | $1 \le n, m \le 100\,000$ | $C = 10^9$ | 所有塔的上端点共线于同一条水平直线上 | | | 7 | 21 | $1 \le n, m \le 100\,000$ | $C = 10^9$ | | 1–6 | | 8 | 17 | $1 \le n, m \le 400\,000$ | $C = 10^9$ | | 1–7 | 翻译由 ChatGPT-5 完成