题意重述

给定序列 $a_1, a_2, \dots, a_n$。
对于每个询问 $[l, r]$，要求：

$$\text{ans}(l,r) = \sum_{l \le s \le t \le r} \min_{s \le k \le t} a_k $$

即：区间 $[l, r]$ 的所有子区间的最小值之和。

有 $q$ 个询问，$q$ 很大（可达 $10^7$），$n$ 可达 $3\times 10^6$，因此必须用 $O(1)$ 或 $O(\log n)$ 时间 回答每个询问，预处理复杂度也要尽量低。

---

第一步：转化为历史问题

对于固定 $r$，设

$$F_r(l) = \text{ans}(l,r)$$

则询问是求 $F_r(l)$。

我们考虑对右端点 $r$ 递增处理，维护当右端点为 $r$ 时，所有左端点 $l$ 的答案 $F_r(l)$。

---

第二步：从 $F_{r-1}(l)$ 到 $F_r(l)$

当右端点从 $r-1$ 增加到 $r$ 时，新增的子区间是所有 $[s, r]$（$s \le r$）。

对于固定的左端点 $l$，$F_r(l)$ 相比于 $F_{r-1}(l)$ 增加了：

$$\sum_{s=l}^{r} \min_{s \le k \le r} a_k$$

这个新增量不好直接加，我们换一种方式。

---

第三步：用单调栈维护最小值控制区间

经典问题：对于每个 $r$，我们要快速知道以 $r$ 为右端点的所有子区间的最小值之和。

设 $g(r)$ 表示以 $r$ 为右端点的所有子区间的最小值之和：

$$g(r) = \sum_{s=1}^{r} \min_{s \le k \le r} a_k$$

那么显然：

$$F_r(l) = \sum_{t=l}^{r} g(t) - \sum_{t=l}^{r-1} g(t) \text{ 的某种前缀和} $$

更直接地，我们可以直接维护 $S(r) = \sum_{t=1}^{r} g(t)$，那么：

$$\text{ans}(l,r) = \sum_{t=l}^{r} g(t) \quad\text{???} $$

不对，这样会多算。让我们仔细推导。

---

正确推导：
$\text{ans}(l,r) = \sum_{l \le s \le t \le r} \min_{s\le k\le t} a_k$。
交换求和顺序，先固定右端点 $t$：

$$\text{ans}(l,r) = \sum_{t=l}^{r} \sum_{s=l}^{t} \min_{s \le k \le t} a_k $$

定义 $h(t, s) = \min_{s\le k\le t} a_k$，则：

$$\text{ans}(l,r) = \sum_{t=l}^{r} \sum_{s=l}^{t} h(t,s) $$

那么如果我们能对每个 $t$ 维护 $G_t(x) = \sum_{s=1}^{x} h(t,s)$，就可以用 $G_t(l-1)$ 求出第二层和。

但维护 $G_t(x)$ 对所有 $t$ 不现实。

---

第四步：转化为前缀和差分

设 $P(r) = \text{ans}(1, r)$，即整个前缀 $[1,r]$ 的所有子区间最小值之和。

那么：

$$\text{ans}(l,r) = P(r) - P(l-1) - \text{“左端点在 $l$ 左边且右端点在 $l$ 到 $r$ 的子区间的最小值之和”} $$

这个“多余部分”不好直接减。

更常见的方法：莫队 或 分治 在 $q$ 很大时不行，必须 $O(1)$ 查询。

---

第五步：经典算法：离线 + 单调栈 + 区间历史和维护

已知一个经典解法（类似“所有子区间最小值之和”的拓展）：

对于每个位置 $i$，考虑 $a_i$ 作为最小值的影响区间。
设 $L_i$ 是 $i$ 左边第一个 $< a_i$ 的位置（不存在则为 $0$），
$R_i$ 是 $i$ 右边第一个 $< a_i$ 的位置（不存在则为 $n+1$）。

那么 $a_i$ 作为最小值的区间 $[s,t]$ 必须满足 $L_i < s \le i \le t < R_i$。

---

对询问的贡献

对于一个询问 $[l,r]$，$a_i$ 的贡献是：

• 当 $l \le s \le i \le t \le r$ 且 $[s,t]$ 在 $(L_i, R_i)$ 内时，$a_i$ 是该区间的最小值。
• 符合条件的 $(s,t)$ 对数 = $(i - \max(l, L_i+1) + 1) \times (\min(r, R_i-1) - i + 1)$，如果这个值 $>0$。

因此：

$$\text{ans}(l,r) = \sum_{i=1}^{n} a_i \cdot \max(0, i - \max(l, L_i+1) + 1) \cdot \max(0, \min(r, R_i-1) - i + 1) $$

这个式子可以拆成多个部分，用 二维前缀和 或 扫描线 + 数据结构 处理。

---

第六步：具体拆分

令 $A_i = L_i+1$，$B_i = R_i-1$。
则 $a_i$ 对询问 $[l,r]$ 有贡献的条件：

1. $l \le i \le r$
2. $l \le A_i \le i$（自动满足 $A_i \le i$）
3. $i \le B_i \le r$

贡献值为 $a_i \cdot (i - \max(l, A_i) + 1) \cdot (\min(r, B_i) - i + 1)$。

---

拆成四种情况（根据 $l$ 与 $A_i$、$r$ 与 $B_i$ 的关系）：

1. $l \le A_i$ 且 $r \ge B_i$：贡献 = $a_i \cdot (i-A_i+1) \cdot (B_i-i+1)$
2. $l \le A_i$ 且 $r < B_i$：贡献 = $a_i \cdot (i-A_i+1) \cdot (r-i+1)$
3. $l > A_i$ 且 $r \ge B_i$：贡献 = $a_i \cdot (i-l+1) \cdot (B_i-i+1)$
4. $l > A_i$ 且 $r < B_i$：贡献 = $a_i \cdot (i-l+1) \cdot (r-i+1)$

这四种情况分别对应 $(l,r)$ 落在某个二维平面的某个矩形区域。
我们可以把询问 $(l,r)$ 看作平面上的点，每个 $i$ 贡献是这些区域上的 $a_i$ 乘以一个关于 $l,r$ 的一次或二次函数。

---

第七步：用二维差分累加

以情况 4 为例：条件 $l > A_i$ 且 $r < B_i$，且 $l \le i \le r$。

贡献 = $a_i \cdot (i-l+1)(r-i+1)$
= $a_i \cdot [ (i+1)(-i+1) + (i+1)r + (-i+1)(-l) + r(-l) ]$
实际上展开： $(i-l+1)(r-i+1) = (i+1)(-i+1) + (i+1)r + l(i-1) - lr$
更规范展开：

$$= (i+1)(r-i+1) - l(r-i+1)$$

再展开 $(i+1)(r-i+1) = (i+1)r - i(i+1) + i+1$，仍复杂。

更好的办法：我们直接维护 $l$ 和 $r$ 的乘积项、一次项、常数项系数。

令： 贡献 $= a_i \cdot [ (i+1)(r-i+1) - l(r-i+1) ]$
$= a_i \cdot [ (i+1)r - (i+1)i + i+1 - lr + l i - l ]$

所以：

• $lr$ 项系数：$-a_i$
• $r$ 项系数：$a_i(i+1)$
• $l$ 项系数：$a_i(i-1)$
• 常数项：$a_i(-i^2 - i + i + 1 - ???)$ 先不细算，反正可以统一。

类似地，其他情况也可拆成 $lr, l, r, 1$ 的线性组合。

这样，我们可以对二维平面做 矩形加一个多项式，最后询问时求该点的多项式值。

矩形加多项式可以用 二维差分（四阶差分）实现。

---

第八步：算法步骤

1. 用单调栈 $O(n)$ 求出 $L_i, R_i$。
2. 对每个 $i$，根据 $A_i = L_i+1, B_i = R_i-1$，确定四个矩形区域（对应上述四种情况），在每个矩形上对系数数组 $c_{lr}, c_l, c_r, c_1$ 做差分修改。
3. 做完所有 $i$ 的更新后，对系数数组做二维前缀和，得到每个 $(l,r)$ 点的四个系数。
4. 生成询问 $(l,r)$（用给定随机函数），计算 $ans(l,r) = c_{lr}[l][r] \cdot lr + c_l[l][r] \cdot l + c_r[l][r] \cdot r + c_1[l][r]$。
5. 累加所有询问答案，取模 $10^9+7$。

---

第九步：复杂度分析

• 预处理 $L_i,R_i$：$O(n)$
• 每个 $i$ 更新四个矩形：每个矩形 $O(1)$ 差分修改（二维差分需在矩形四个角加减）
• 二维前缀和：$O(n^2)$？不行，$n$ 太大（$3\times 10^6$），不能开 $n^2$ 数组。

---

第十步：优化空间

由于 $q$ 很大但 $n$ 也很大，不能开 $n^2$ 数组。
必须在线回答询问，即给定 $(l,r)$ 能快速计算答案。

注意到每个 $i$ 贡献是一个分段函数，询问 $(l,r)$ 时可以快速求和：
我们可以将贡献公式写成：

$$\text{ans}(l,r) = \sum_{i=l}^{r} a_i \cdot (i - \max(l, A_i) + 1) \cdot (\min(r, B_i) - i + 1) $$

这个求和可以通过预处理一些前缀和，在 $O(\log n)$ 内完成。

具体：

• 对固定的 $l$，当 $i$ 从 $l$ 到 $r$ 变化时，$\max(l, A_i)$ 要么是 $l$，要么是 $A_i$，分界点在 $A_i \ge l$ 的位置。
• 类似地，$\min(r, B_i)$ 要么是 $r$，要么是 $B_i$。

因此可以拆成至多四个部分，每部分内 $i$ 满足固定 $\max$ 和 $\min$，贡献可以写成 $a_i \cdot (i - C + 1) \cdot (D - i + 1)$，展开后是 $a_i$ 的一次和二次前缀和。

---

第十一步：实现方案

预处理：

1. 对每个 $i$，存 $A_i, B_i$。
2. 预处理 $a_i$、$i \cdot a_i$、$i^2 \cdot a_i$ 等前缀和。
3. 对每个可能的 $l$，需要快速找到 $i$ 满足 $A_i \ge l$ 的分界点，这可以通过对 $A_i$ 排序并建立数据结构（如可持久化线段树）实现。

但由于 $n$ 很大且 $q$ 很大，$O(\log n)$ 每个询问可能仍太慢（$10^7 \log n$ 约 $2\times 10^8$ 操作，勉强可过）。

---

第十二步：最终策略

综合以上，最优做法：

• 离线所有询问（用生成器生成）。
• 用扫描线按 $r$ 递增处理询问，同时维护一个数据结构支持区间加一次函数、区间查询和。
• 当右端点 $r$ 增加时，更新所有 $B_i \ge r$ 的 $i$ 的贡献。
• 用线段树维护当前 $r$ 下每个 $l$ 的答案 $F_r(l)$，支持区间加二次函数（关于 $l$）。

这样每个 $i$ 在 $r$ 从 $i$ 到 $B_i$ 期间贡献一个关于 $l$ 的一次函数，加到线段树区间 $[A_i, i]$ 上。

每个询问就是查询线段树位置 $l$ 的值。

复杂度：$O((n+q) \log n)$，$q=10^7$ 时 $\log n$ 约 $22$，总操作 $2.2\times 10^8$，在优化良好的 C++ 中可过。

---

总结

本题难点：

1. 询问次数极大，需 $O(\log n)$ 或更快回答。
2. 将区间子区间最小值求和转化为每个位置作为最小值的贡献。
3. 利用单调栈求控制区间。
4. 通过差分或扫描线+数据结构处理二维贡献。

最终方案：扫描右端点，用线段树维护左端点答案，区间加一次函数，实现 $O((n+q)\log n)$。