本文共 839 字，大约阅读时间需要 2 分钟。

原题的题意可以理解为求所有子区间的最大值减去最小值的和。 即所有子区间的最大值减去最小值。 我们考虑用单调栈求解。 维护两个数组 l[i] ,r[i]。表示当前元素作为最大值所能到达的左边和右边的下标是多少（当前元素作为最值），用单调栈维护。 先正着维护左区间，再倒着维护右区间。 维护时的操作：当前元素大于前一个元素时，下标存上一个l[i]的下标，一直循环下去，直到当前数小于前面比较的数，左区间维护成功。右区间的维护是同样的道理。

维护最小值只需要把原来数组全部变成相反数，可以找到最小值。

求和：排列组合的思想，当前数作为最大值，左边到l[i] ,右边到r[i]，左边的情况有i-l[i]种，右边情况有r[i]-i种，相乘即可。

#include
   
    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
    
     >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<
     
      <
     
    
   

转载地址：http://gnrq.baihongyu.com/