思路

问题可以转化为 求每个区间(区间长度大于1的区间)的最大值 与 最小值，最大值之和 减去 最小值之和 就是答案

注：下面所提区间，默认 区间长度大于 1

如何求 最大值之和 与 最小值之和

1：枚举每个区间，时间复杂度 O(n^2)  ==>  超时
2：枚举每个值，假设该值为区间最大值
此时 num_1 * maxm_1 + num_2 * maxm_2 + ... + num_n * maxm_n = 最大值之和 
num_i 表示 maxm_i 这个值 可以在 num_i 个区间里作为最大值

求最小值之和 同理

求 num_i ：

不妨令 a[i] 为最大值，我们求出 a[i] 的左右边界 l[i]、r[i]：左边/右边第一个比a[i]大的值的位置
则 num_i = (r[i] - l[i] - 2) + (i - l[i] - 1) * (r[i] - i - 1)
r[i] - l[i] - 2 ：a[i] 为区间端点时的情况
r[i] - i - 1    : a[i] 为区间内部点时的情况

求 l[i] 与 r[i] ：

由于 l[i]、r[i] 的性质：左边/右边第一个比a[i]大的值的位置， 我们可以使用单调栈来求l[i]、r[i]
从左到右 跑一遍求出 l[i]，从右到左跑一遍求出 r[i]

关于代码中两处位置 一个加等号 一个不加的解释

若存在 a[i] = a[i+1] ，比如 1、5、5 ：a[2] = a[3]
对于 样例 1、5、5，我们应该得到的答案是 8，但两处都加等号实际得到的却是 13

这是因为此时：
对于区间 [1,3] 有两个最大值 5，一个最小值 1
对于区间 [2,3] 有两个最大值 5，两个最小值 5
对于区间 [1,2] 有一个最大值 5，一个最小值 1

最大值之和为：5*2 + 5*2 + 5 = 25
最小值之和为：1 + 5*2 + 1 = 12
结果：25 - 12 = 13 != 8（预期结果）

所以我们需要一个加等于号 一个不加，避免上述现象，
可验证 对于栗子:1、5、5，一个加等于号 一个不加 得到的结果是 8，与预期一致

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6+10;

int l[N],r[N];
int stk[N],a[N];
int n,hh;

ll solve(){
    hh=0;
    stk[++hh]=0;
    a[0]=1e6;
    for(int i=1;i<=n;i++) {
        while(hh&&a[i]>=a[stk[hh]]) hh--;     // 一个加等于号
        l[i]=stk[hh];
        stk[++hh]=i;
    }

    hh=0;
    stk[++hh]=n+1;
    a[n+1]=1e6;
    for(int i=n;i>=1;i--) {
        while(hh&&a[i]>a[stk[hh]]) hh--;  // 一个不加等于号
        r[i]=stk[hh];
        stk[++hh]=i;
    }

    ll res=0;
    for(int i=1;i<=n;i++){
        res+=(ll)a[i]*(r[i]-l[i]-2);    //避免爆掉 int
        res+=(ll)a[i]*(i-l[i]-1)*(r[i]-i-1);
    }
    return res;
}

int main(){
    int T;
    cin>>T;

    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        ll res=solve();
        for(int i=1;i<=n;i++) a[i]=-a[i];  // a[i] 变为相反数后 求出的最大值 是 原先的最小值
        cout<<res+solve()<<endl;
    }

    return 0;
}