题解 | #区区区间间间#

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
int t,n;
int a[N];
/*
1.观察到式子就是求区间的最大值减最小值的和，我们分别求最大值和求最小值
2.如果直接暴力求每个区间的最值，显然会超时
3.于是我们进行思维的转换：以a[i]为最大值，可控制的最长区间，
然后算这个最长区间有几个子区间，而每个子区间都能带来a[i]的贡献
4.即去找a[i]左边第一个大于它的数的位置和a[i]右边第一个大于它的数的位置
5.使用l[i]和r[i]数组分别存储
6.同时可以发现，当a[i]比这个数大时，那么a[i]一定比它所控制的区间大
7.在找i左边最大时，用一个指针j指向i-1,当a[i]>=a[j]时，j指针指向区间左边界，
即j = l[j]，直到a[i]<a[j],而停住的地方就是第一个大于它的值。找右边界同理。
8.而找最小值时，只要让a[i]数组取反即可
*/
int solve(){
    int sum = 0ll;
    int l[N] = {0},r[N] = {0};
    l[1] = 0;r[n] = n + 1;
    for (int i=1;i<=n;i++){
        int j = i - 1;
        while (j>0 && a[i]>=a[j]){
            j = l[j];
        }
        l[i] = j;
    }
    //for (int i=1;i<=n;i++) printf("l[%lld] = %lld\n",i,l[i]);
    /*
    为什么要上面是a[i]>=a[j]但下面是a[i]>a[j]?因为算贡献的时候，如果都有=，
    算贡献的时候,两边是会重复算的,所以我们只要一边有等于就好
    (即下面加等于而上面没有效果是一样的)
    */
    for (int i=n;i>=1;i--){
        int j = i + 1;
        while (j<=n && a[i]>a[j]){
            j = r[j];
        }
        r[i] = j;
    }
    //for (int i=1;i<=n;i++) printf("r[%lld] = %lld\n",i,r[i]);
    //算贡献
    for (int i=1;i<=n;i++){
        //如果a[i]为端点,它可以算r[i]-l[i]-2个点
		sum += a[i] * (r[i]-l[i]-2);
        //如果a[i]不为端点,其他点为端点,区间个数就是a[i]左边的点个数乘上a[i]右边的点个数
		sum += a[i] * (i-l[i]-1) * (r[i]-i-1);
        //cout<<sum<<endl;
    }
    return sum;
}
signed main(){
    scanf(" %lld",&t);
    while (t--){
        scanf(" %lld",&n);
        for (int i=1;i<=n;i++) scanf(" %lld",a+i);
        int ans = 0ll;
        ans += solve();
        for (int i=1;i<=n;i++) a[i] = -a[i];
        ans += solve();
        printf("%lld\n",ans);
    }
}