← 返回题目列表

Codeforces · 1635/F

F. 最近的一对

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

$$$OX$$$ 轴上有 $$$n$$$ 个加权点。第 $$$i$$$ 个点的坐标和权重分别为 $$$x_i$$$ 和 $$$w_i$$$。所有点都有不同的坐标和正权重。此外,$$$x_i < x_{i + 1}$$$ 对于任何 $$$1 \leq i < n$$$ 成立。

第 $$$i$$$ 个点和第 $$$j$$$ 个点之间的加权距离定义为 $$$|x_i - x_j| \cdot (w_i + w_j)$$$,其中 $$$|val|$$$ 表示 $$$val$$$ 的绝对值。

您应该回答 $$$q$$$ 查询,其中第 $$$i$$$ 查询要求以下内容:查找子数组 $$$[l_i,r_i]$$$ 中的点中所有不同点对之间的最小加权距离。

输入

第一行包含 2 个整数 $$$n$$$ 和 $$$q$$$ $$$(2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5)$$$ — 点数和查询数。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$w_i$$$ $$$(-10^9 \leq x_i \leq 10^9; 1 \leq w_i \leq 10^9)$$$ — 坐标和权重第 $$$i$$$ 个点。

保证分数按 $$$x$$$ 的升序给出。

然后是 $$$q$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \leq l_i < r_i \leq n)$$$ — 第 $$$i$$$ 查询的给定子数组。

输出

对于每个查询输出一个整数,给定子数组中所有一对不同点之间的最小加权距离。

示例

输入 #1

5 5
-2 2
0 10
1 1
9 2
12 7
1 3
2 3
1 5
3 5
2 4

输出 #1

9
11
9
24
11

注意

对于第一个查询,最小加权距离位于点 $$$1$$$ 和 $$$3$$$ 之间,等于 $$$|x_1 - x_3| \cdot (w_1 + w_3) = |-2 - 1| \cdot (2 + 1) = 9$$$。

对于第二个查询,最小加权距离位于点 $$$2$$$ 和 $$$3$$$ 之间,等于 $$$|x_2 - x_3| \cdot (w_2 + w_3) = |0 - 1| \cdot (10 + 1) = 11$$$。

对于第四个查询,最小加权距离位于点 $$$3$$$ 和 $$$4$$$ 之间,等于 $$$|x_3 - x_4| \cdot (w_3 + w_4) = |1 - 9| \cdot (1 + 2) = 24$$$。