区间最大利润

【题目描述】

给定一个长度为 $n$ 的数列 $A_1, A_2, \dots, A_n$，其中 $A_i$ 表示第 $i$ 天的价格。

一笔交易的利润定义为「先买后卖」的差价：在时刻 $i$ 买入、时刻 $j$ 卖出（$i < j$）可获得 $A_j - A_i$ 的利润。

现在有 $q$ 次询问，每次给定 $l, r$，请求出只在区间 $[l, r]$ 内交易时能获得的最大利润，即求

【输入】

第一行两个整数 $n, q$，分别表示天数与询问次数。

第二行 $n$ 个整数 $A_1, A_2, \dots, A_n$。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

【输出】

对于每次询问输出一行一个整数，表示区间 $[l, r]$ 内的最大利润。

【数据范围】

$2 \leqslant n \leqslant 10^5$

$1 \leqslant q \leqslant 10^5$

$1 \leqslant A_i \leqslant 10^9$

$1 \leqslant l < r \leqslant n$

【输入样例】

6 4
5 3 1 3 4 3
1 6
1 4
3 6
4 5

【输出样例】

3
2
3
1

【样例解释】

• 询问 $[1,6]$：在第 3 天买入（价格 $1$）、第 5 天卖出（价格 $4$），利润 $4-1=3$；
• 询问 $[1,4]$：区间为 $5,3,1,3$，在第 3 天买入（$1$）、第 4 天卖出（$3$），利润 $3-1=2$；
• 询问 $[3,6]$：区间为 $1,3,4,3$，在第 3 天买入（$1$）、第 5 天卖出（$4$），利润 $3$；
• 询问 $[4,5]$：区间为 $3,4$，利润 $4-3=1$。

【提示】

• 注意利润可能为负数：当区间内价格严格递减时，最优仍必须先买后卖，此时答案是最小的负数（例如区间为 $4,3,2$ 时答案为 $-1$）。
• 每次询问相互独立，区间之外的价格不能参与交易。
• 直接对每次询问扫描区间是 $O(nq)$，无法通过；需要考虑能快速合并区间信息的数据结构。

【来源】

ROJ 原创（配套 1417 最大利润 的区间询问加强版）