2595. 区间极差乘和
2000ms
512MB
简单
题目描述
给定一个长度为 `n` 的整数序列 `a_1, a_2, ..., a_n`。
对于每一个非空连续子段 `[l, r]`，定义：
- `mx(l,r)` 为子段最大值；
- `mn(l,r)` 为子段最小值；
- `sum(l,r)` 为子段元素和。
该子段的贡献为：
$$
(mx(l,r) - mn(l,r)) \times sum(l,r)
$$
请求出所有非空连续子段的贡献之和，对 `1,000,000,007` 取模。
注意：最终答案可能为负数，请输出模意义下的非负结果。
输入格式
第一行一个整数 `n`。
第二行 `n` 个整数 `a_1, a_2, ..., a_n`。
输出格式
输出一个整数，表示答案对 `1,000,000,007` 取模后的非负结果。
样例 1
输入 (Input)
输出 (Output)
样例 2
输入 (Input)
输出 (Output)
样例说明
### 样例解释 1
所有子段如下：
- `[1,1]`：`(1-1)*1 = 0`
- `[2,2]`：`(3-3)*3 = 0`
- `[3,3]`：`(2-2)*2 = 0`
- `[1,2]`：`(3-1)*(1+3) = 2*4 = 8`
- `[2,3]`：`(3-2)*(3+2) = 1*5 = 5`
- `[1,3]`：`(3-1)*(1+3+2) = 2*6 = 12`
总和为 `8 + 5 + 12 = 25`。
### 样例解释 2
- `[-1]`：贡献 0
- `[2]`：贡献 0
- `[-1,2]`：`(2 - (-1)) * (1) = 3`
答案为 3。
- $1 <= n <= 10^6$
- $-10^9 <= a_i <= 10^9$
- 模数为 `MOD = 1,000,000,007`
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功