好题啊。
题意
给定 \(n\) 个二元组 \((x_i, w_i)\)，保证 \(x\) 升序。有 \(m\) 个询问 \([l, r]\)，对于每个询问求出：
\[\min\limits_{l \le i < j \le r}(x_j - x_i) \cdot (w_i + w_j) \]题解
一个精妙的结论：
- 设 \(L_i\) 表示 \(i\) 左边第一个满足 \(w_j \le w_i\) 的 \(j\)，\(R_i\) 表示 \(i\) 右边第一个满足 \(w_j \le w_i\) 的 \(j\)。
- 一个询问的答案的最优 \((i, j)\) 一定在 \((x, R_x)\) 或者 \((L_x, x)\) 处取到。
证明：反证法。假设最优处在 \((i, j)\) 且 \(i \neq L_j \land R_i \neq j\)。那么一定有 \((i, L_j)\) 或者 \((R_i, j)\) 更优，原因如下：
因为 \(w_{L_j} \le w_j\)，\((w_i + w_{L_j}) \le (w_i + w_j)\) 并且还有 \((x_{L_j} - x_i) < (x_j - x_i)\)。故乘积更小。
所以 \((i, j)\) 有更优处，与假设矛盾。证毕
于是有了这个结论之后，不难用树状数组维护答案，复杂度 \(O(n \log n)\)。
这道题的结论同样启示我们，对于这种 RMQ 问题（或者取全局最小值的问题），都要尝试思考一下最值在哪些位置取得，这些位置的性质是什么等等。
代码：