原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：求一个具体数值
1.2 题目背景、允许、禁止与限制
背景：有一个有 nnn 个数的序列 aaa
允许：定义一个子序列的权值为子序列中最大值与最小值的差，求出所有连续子序列的权值之和
禁止：
限制：连续子序列
1.3 题目数据范围与猜测
2≤n≤3×105⟶O(n)2 \le n \le 3\times10^5 \longrightarrow O(n)2≤n≤3×105⟶O(n)
1.4 一句话概括题意
有一个序列，定义一个子序列的权值为子序列中最大值与最小值的差，求出所有连续子序列的权值之和
2 题目破题推导
> 注：以下六种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
首先我们要知道：要想使最终连续子序列权值之和更大，那就必须要使包含 aia_iai 的区间越长（这样对于 aia_iai 来说，包含 aia_iai 的连续子序列的个数就越多）
那么，假设区间 [i,j][i,j][i,j] 中的某个点 kkk 保证 aka_kak 是区间 [i,j][i,j][i,j] 对应 aaa 数组中元素中的最大值，并且这个区间是符合条件的最长区间，说明 ai−1a_{i-1}ai−1 与 aj+1a_{j + 1}aj+1 均 >ak>a_k>ak
接着，假设区间 [i,j][i,j][i,j] 中的某个点 kkk 保证 aka_kak 是区间 [i,j][i,j][i,j] 对应 aaa 数组中元素中的最小值，并且这个区间是符合条件的最长区间，说明 ai−1a_{i-1}ai−1 与 aj+1a_{j + 1}aj+1 均 <ak<a_k<ak
那我们反过来思考
如果 aka_kak 左边第一个比其小的元素位置是 iii，右边第一个比其小的元素位置是 jjj，则区间 [i+1,j−1][i+1,j-1][i+1,j−1] 就是以 aka_kak 为最小值的最长区间
如果 aka_kak 左边第一个比其大的元素位置是 iii，右边第一个比其大的元素位置是 jjj，则区间 [i+1,j−1][i+1,j-1][i+1,j−1] 就是以 aka_kak 为最大值的最长区间
2.3 以终为始、以始为终
2.4 数学
2.5 分情况考虑
2.6 手动推导
2.7 边界测试
3 模型匹配
先提取关键词：左边第一个比其大 右边第一个比其大 右边第一个比其小 左边第一个比其小
是 单调栈\huge{单调栈}单调栈
4 具体方案
4.1 单调栈维护
维护四个单调栈，分别代表左边第一个比其大、右边第一个比其大、右边第一个比其小、左边第一个比其小
4.2 计算答案
因为 a+(b−c)=a+b−ca + (b-c)=a+b-ca+(b−c)=a+b−c
因此维护一个ans变量，记录最终答案
我们知道如果 aka_kak 被包含在区间 [l,r][l,r][l,r] 内且是最大值，最终它对于这段区间的贡献就是 ak×l×ra_k \times l \times rak ×l×r
我们知道如果 aka_kak 被包含在区间 [l,r][l,r][l,r] 内且是最小值，最终它对于这段区间的贡献就是 −(ak×l×r)-(a_k \times l \times r)−(ak ×l×r)
5 最终代码（禁止抄袭，仅用于参考）
