区区区间间间

思路：
就是求所有子区间(区间长度大于1的子区间)的最大值减去最小值的和是多少。
我们对原式子拆分一下可得
其中max(l,r)表示区间l到r的最大值，min(l,r)表示区间l到r的最小值。
那么问题就转化为 求所有区间长度大于1的子区间的最大值之和/最小值之和。
暴力的方法就是两个for枚举起点和终点去计算，会TLE
考虑单调栈，单调栈维护什么？ 维护以a[i]为区间的最大值，往左右两边去更新拓展。
正着跑一次单调栈，倒着跑一次单调栈就能维护出来l和r数组。
其中l[i]表示以a[i]为最大值，左边最多延伸到l[i]，r[i]表示以a[i]为最大值，右边最多延伸到r[i]
然后怎么计算呢？
右两种情况。
① a[i]作为一个区间的端点，那么可以选择的区间另一个端点就是r[i]-l[i]。
② a[i]作为区间中的一点，也就是区间的端点都没选。那么就是在l[i]到i之间选一个作为左端点，r[i]-i之间选一个作为右端点，乘法原理可得区间的个数为 (r[i]-i) * (i-l[i])
这样就处理出来拆分出来的和式的第一部分了。
第二部分怎么求？
让a[i]=-a[i]，那么求最小值，就等于取反后的求最大值，在跑一下上面的过程就好了。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int a[1<<17];
int l[1<<17],r[1<<17];
int n;
int  solve(){

     for(int i=1;i<=n;i++){
            int j=i;
            while(j>1 && a[j-1]<=a[i])
                    j=l[j-1];
            l[i]=j;
        }
        for(int i=n;i;i--){
            int j=i;
            while(j<n && a[j+1]<a[i])
                 j=r[j+1];
            r[i]=j;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            //cout<<l[i]<<" "<<r[i]<<endl;
             ans += a[i]*(r[i]-l[i]);
             ans += a[i]*(i-l[i])*(r[i]-i);
        }
    return ans;
}
signed main(){

    int t;cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int ans=solve();
        for(int i=1;i<=n;i++) a[i]=-a[i];
        cout<<ans+solve()<<endl;
    }
    return 0;
}