P11325 【MX-S7-T3】「SMOI-R2」Monotonic Queue
题目背景
原题链接：。
题目描述
给定一个正整数 $n$ 和 $n$ 个整数 $c_1, \ldots, c_n$（这些数可能为负），以及一个 $1 \sim n$ 的排列 $(a_1, \ldots, a_n)$。
为了考验朋友小 L 的能力，你设计了一道这样一道题目：
> 给定 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$，它们满足以下条件：
> - $1 \leq l_i \leq r_i \leq n$；
> - $l_1 \leq l_2 \leq \dots \leq l_n$；
> - $r_1 \leq r_2 \leq \dots \leq r_n$。
>
> 对于每个区间 $[l_i, r_i]$，小 L 需要求出 $a_{l_i \sim r_i}$ 中最大值的位置，记为 $b_i$。
小 L 准备使用**单调队列**来高效地完成这个题目。他的算法核心伪代码如下：
---
---
对应的 C++ 实现代码如下：
```cpp
deque Q;
l[0] = r[0] = sum = 0;
for (int i = 1; i
输入格式
无
输出格式
无
说明/提示
**【样例解释 #1】**
若所有区间都为 $[5,5]$，则算法结束后 `sum` 的值为 $308$。可以证明没有使 `sum` 更大的方案。
**【样例解释 #2】**
若所有区间都为 $[1,1]$，则算法结束后 `sum` 的值为 $0$。可以证明没有使 `sum` 更大的方案。
**【样例解释 #3】**
若 $5$ 个区间分别为 $[2,2]$、$[2,2]$、$[2,4]$、$[2,4]$、$[2,4]$，则算法结束后 `sum` 的值为 $396$。可以证明没有使 `sum` 更大的方案。
**【样例 #4】**
见附件中的 `queue/queue4.in` 与 `queue/queue4.ans`。
该组样例满足测试点 $2\sim 5$ 的约束条件。
**【样例 #5】**
见附件中的 `queue/queue5.in` 与 `queue/queue5.ans`。
该组样例满足测试点 $8\sim 12$ 的约束条件。
**【样例 #6】**
见附件中的 `queue/queue6.in` 与 `queue/queue6.ans`。
该组样例满足测试点 $15\sim 16$ 的约束条件。
**【数据范围】**
对于所有测试数据，保证：$2\le n\le 5\times 10^5$，$\lvert c_i \rvert\le 10^9$，$1 \le a_i \le n$，$(a_1, \ldots, a_n)$ 为 $1\sim n$ 的排列。
|测试点编号|$n\le $|特殊性质|
|:-:|:-:|:-:|
|$1$|$6$|无|
|$2\sim 5$|$15$|无|
|$6\sim 7$|$5\times 10^5$|A|
|$8\sim 12$|$5000$|无|
|$13\sim 14$|$2\times 10^5$|B|
|$15\sim 16$|$2\times 10^5$|C|
|$17\sim 19$|$10^5$|无|
|$20\sim 25$|$5\times 10^5$|无|
- 特殊性质 A：满足 $c_i > 0$ 的 $i$ 不超过 $1$ 个。
- 特殊性质 B：满足 $c_i < 0$ 的 $i$ 不超过 $2$ 个。
- 特殊性质 C：满足 $c_i < 0$ 的 $i$ 不超过 $10$ 个。