题目链接：https://ac.nowcoder.com/acm/problem/15815

题意：让求某个长度为n的数字序列中，所有连续子序列的最大值-最小值之和：\(\sum_{len=1}^{len=n}{Maxnum-Minnum}\)

思路:相当于计算a[i]作为最大值出现的次数-a[i]作为最小值出现的次数，也就是计算a[i]对于最后结果的贡献，由于是连续序列，O(n)时间复杂度中计算包含a[i]的连续序列中作为最小值或者最大值出现的次数，可以使用单调栈进行计算。注意:对于a[i]，如果计算其作为最大值的次数，往左找到比a[i]值大的位置a[l],往右找到比a[i]值大的位置a[r]，则构成的序列个数为(l-i+1)*(r-i+1)

代码：

#include<bits/stdc++.h>

using namespace std;
int a[(int)1e6+6];
int n;
int s[(int)1e6+5],w[(int)1e6+6];
long long  sta(int t){
    long long  ans=0;
    int tot=0;
    if(t){s[0]=0;a[n]=0;}
    else {s[0]=0x3f3f3f;a[n]=0x3f3f3f;}
    for(int i=0;i<=n;i++){
        int wd=1;//右边初始长度，即自身
        while(t==1 ? a[i]<s[tot]:a[i]>s[tot]){
            ans+=1LL*wd*s[tot]*w[tot];//注意此处：计算作为极值所处的连续子序列数目
            wd+=w[tot];
            tot--;
        }
        s[++tot]=a[i];w[tot]=wd;
    }
    return ans;
}
int main (){
    
    while(cin>>n){
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
        cout<<sta(0)-sta(1)<<endl;
    }
    
    return 0;
}