Closest Pair
题意翻译
- 给定 $n(2 \le n \le 3\times 10^5)$ 个二元组 $(x_i,w_i)$,其中 $|x_i|\le 10^9$,$1\le w_i \le 10^9$。
- 输入中二元组按照 $x_i$ 严格递增排序给出。
- 给出 $q(1\le q \le 3\times 10^5)$ 次询问,每次询问给出 $l,r(1\le l<r \le n)$,你需要输出:
$$
\min_{l\le i<j\le r} |x_i-x_j| \cdot (w_i+w_j)
$$
题目描述
There are $ n $ weighted points on the $ OX $ -axis. The coordinate and the weight of the $ i $ -th point is $ x_i $ and $ w_i $ , respectively. All points have distinct coordinates and positive weights. Also, $ x_i < x_{i + 1} $ holds for any $ 1 \leq i < n $ .
The weighted distance between $ i $ -th point and $ j $ -th point is defined as $ |x_i - x_j| \cdot (w_i + w_j) $ , where $ |val| $ denotes the absolute value of $ val $ .
You should answer $ q $ queries, where the $ i $ -th query asks the following: Find the minimum weighted distance among all pairs of distinct points among the points in subarray $ [l_i,r_i] $ .
输入输出格式
输入格式
The first line contains 2 integers $ n $ and $ q $ $ (2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5) $ — the number of points and the number of queries.
Then, $ n $ lines follows, the $ i $ -th of them contains two integers $ x_i $ and $ w_i $ $ (-10^9 \leq x_i \leq 10^9; 1 \leq w_i \leq 10^9) $ — the coordinate and the weight of the $ i $ -th point.
It is guaranteed that the points are given in the increasing order of $ x $ .
Then, $ q $ lines follows, the $ i $ -th of them contains two integers $ l_i $ and $ r_i $ $ (1 \leq l_i < r_i \leq n) $ — the given subarray of the $ i $ -th query.
输出格式
For each query output one integer, the minimum weighted distance among all pair of distinct points in the given subarray.
输入输出样例
输入样例 #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
说明
For the first query, the minimum weighted distance is between points $ 1 $ and $ 3 $ , which is equal to $ |x_1 - x_3| \cdot (w_1 + w_3) = |-2 - 1| \cdot (2 + 1) = 9 $ .
For the second query, the minimum weighted distance is between points $ 2 $ and $ 3 $ , which is equal to $ |x_2 - x_3| \cdot (w_2 + w_3) = |0 - 1| \cdot (10 + 1) = 11 $ .
For the fourth query, the minimum weighted distance is between points $ 3 $ and $ 4 $ , which is equal to $ |x_3 - x_4| \cdot (w_3 + w_4) = |1 - 9| \cdot (1 + 2) = 24 $ .