线段树进阶

0x01 李超线段树

FZPJ4519 [2021冬令营模拟] 上古遗迹

【题目背景】
“沙……沙……沙……”独行者的脚步一次次被刻进沙漠中，干冷的风携沙尘在男子的四围穿过。
“该死……这沙尘什么时候才能消停会儿……”男子止不住地咳嗽，随即停了下来，开始查看便携式投影设备上的信息，“应该就在附近了才对……”
就在这时，风尘似乎是要止住，又仿佛是无意地，将不远处那方遗迹显现出来。

【题目描述】
ConneR 所寻找的遗迹是一排高耸的石板。这排石板总共由 \(n\) 块宽度均为 \(1\) 并且无缝隙地竖直矗立在地面上的石板组成，其中从左到右数的第 \(i\) 块石板高度为 \(h_i\)。例如下图是 \(n = 5\) 时这些石板可能的样子（图中每个小正方形面积为 \(1\)）：

ConneR 想要在石板上采集到尽可能多的信息，但他发现自己的信息采集装置的电量只够他采集一块矩形区域的石板信息了。同时，由于信息采集装置的设计缺陷，该装置采集的矩形区域必须是完整的。
ConneR 可以选择采集左下角 \(3 \times 3\) 的一块矩形的信息（下图的红色部分），但不能选择采集左下角一块 \(3 \times 4\) 的矩形的信息，因为第 \(4\) 块石板高度只有 \(2\)。

ConneR 想要问你他在这个遗迹上最大可以采集到多大面积的信息。同时，由于风沙影响了 ConneR 的行动范围，ConneR 会给出你多组询问，每次询问他在一个区间的石板上最多能采集到多大面积的信息。
对于所有测试点，满足 \(1 \le n, m \le 2 \times 10^5，1 \le h_i \le 10^9，1\le l\le r\le n\)。