← 返回题目列表

Codeforces · 500/E

E. 新年多米诺骨牌

中文机器翻译题面 查看原题

庆祝新年,很多人发布多米诺骨牌倒下的视频;以下是其中的列表:https://www.youtube.com/results?search_query=New+Years+Dominos

生活在 2D 世界中的用户 ainta 也将发布一段视频。

二维笛卡尔平面上有 n 个多米诺骨牌。第 i 个多米诺骨牌 (1 ≤ i ≤ n) 可以表示为平行于 y 轴、长度为 li 的线段。多米诺骨牌的最低点位于 x 轴上。我们将第 i 个多米诺骨牌的 x 坐标表示为 pi。多米诺骨牌是一个接一个地放置的,因此 p1 < p2 < ... < pn - 1 < pn 成立。

用户 ainta 想要拍摄多米诺骨牌倒下的视频。为了让多米诺骨牌倒下,他可以将单张多米诺骨牌推到右边。然后,多米诺骨牌会倒下,画出一个圆形的轨道,直到线段与x轴完全重叠。

另外,如果第 s 张多米诺骨牌在倒下时碰到了第 t 张多米诺骨牌,则第 t 张多米诺骨牌也会向右倒下,过程与上述相同。当且仅当表示 s 和 t 的线段相交时,多米诺骨牌 s 才会触及多米诺骨牌 t。

参见上图。如果他将最左边的多米诺骨牌推到右边,它就会倒下,接触到多米诺骨牌 (A)、(B) 和 (C)。结果,多米诺骨牌(A)、(B)、(C)也会向右倒下。然而,多米诺骨牌(D)不会因为推动最左边的多米诺骨牌而受到影响,但最终它会因为第一次被多米诺骨牌(C)接触而倒下。

上图是倒下的多米诺骨牌的例子。每个红色圆圈表示两个多米诺骨牌的碰触。

用户 ainta 有 q 个发布视频的计划。第 j 个多米诺骨牌从推动第 xj 个多米诺骨牌开始,一直持续到第 yj 个多米诺骨牌倒下。但有时候,这样的计划可能无法实现,所以他不得不加长一些多米诺骨牌。将单个多米诺骨牌的长度增加 1 需要花费 1 美元。用户 ainta 想知道对于每个计划,实现它所需的最低成本。计划是独立处理的,即。 e.如果在某些计划中增加多米诺骨牌的长度,则不会影响其在其他计划中的长度。除了第 xj 个多米诺骨牌和第 yj 个多米诺骨牌之外,将倒下的一组多米诺骨牌并不重要,但最初的推动应该在多米诺骨牌 xj 上。

输入

第一行包含一个整数 n (2 ≤ n ≤ 2 × 105)——多米诺骨牌的数量。

接下来的 n 行描述了多米诺骨牌。第 i 行 (1 ≤ i ≤ n) 包含两个空格分隔的整数 pi, li (1 ≤ pi, li ≤ 109) — 第 i 块多米诺骨牌的 x 坐标和长度。保证 p1 < p2 < ... < pn - 1 < pn。

下一行包含一个整数 q (1 ≤ q ≤ 2 × 105) — 计划数量。

接下来 q 行描述了计划。第 j 行 (1 ≤ j ≤ q) 包含两个空格分隔的整数 xj, yj (1 ≤ xj < yj ≤ n)。这意味着第j个计划是,推动第xj张多米诺骨牌,并拍摄视频,直到第yj张多米诺骨牌倒下。

输出

对于每个计划,打印一行包含实现该计划所需的最低成本。如果不需要成本,则打印 0。

示例

输入 #1

6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6

输出 #1

0
1
1
2

注意

考虑这个例子。多米诺骨牌的摆放方式如下图所示。

我们来看看第四个方案。要通过推动第二张多米诺骨牌使第六张多米诺骨牌倒下,第三张多米诺骨牌(其x坐标为4)的长度应增加1,第五张多米诺骨牌(其x坐标为9)应增加1(其他选择是将第四张多米诺骨牌而不是第五张多米诺骨牌也增加1)。然后,多米诺骨牌就会倒下,如下图所示。每个十字表示两个多米诺骨牌之间的接触。