题目:N个整数组成的数组,定义子数组a[i]..a[j]的宽度为:max(a[i]..a[j]) - min(a[i]..a[j]),求所有子数组的宽度和。


题解:首先题目的意思可以转化为求所有的子数组最大值之和减去所有的子数组最小值之和。

那么我们可以通过两次单调栈求得以每个a[i]作为最大以及最小的左右两端能到达的端点。然后求左右端点的时候要注意的一点是确定左边的重复计算或者右边的重复计算,因此通过单调栈计算左右区间的时候需要确定左边或者右边使用等于号(假设我们在右边使用等于号,那么就相当于确定唯一的左区间,右边的区间可以覆盖到相同的更广的位置来计算重复的区间)。

然后以每个a[i]作为贡献的区间的值是多少呢?因为当a[i]作为贡献时子数组区间必过a[i],那么我们只需要在a[i]作为贡献的左区间和右区间任选2个组成区间即为a[i]的贡献,所以是a[i]*(i-l[i]+1)*(r[i]-i+1)。


代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
const int maxn=50005;
int n, data[maxn];
stack<int> ma, mi;
int mal[maxn], mar[maxn], mil[maxn], mir[maxn];
inline int read(){
int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    while(~scanf("%d", &n)){
        while(!ma.empty())ma.pop();
        while(!mi.empty())mi.pop();
        for(int i=1;i<=n;i++){
            data[i]=read();
            while(ma.size()&&data[ma.top()]<=data[i])ma.pop();
            while(mi.size()&&data[mi.top()]>=data[i])mi.pop();
            mal[i]=ma.size()?ma.top()+1:1;
            mil[i]=mi.size()?mi.top()+1:1;
            ma.push(i);
            mi.push(i);
        }
        while(!ma.empty())ma.pop();
        while(!mi.empty())mi.pop();
        for(int i=n;i>=1;i--){
            while(ma.size()&&data[ma.top()]<data[i])ma.pop();
            while(mi.size()&&data[mi.top()]>data[i])mi.pop();
            mar[i]=ma.size()?ma.top()-1:n;
            mir[i]=mi.size()?mi.top()-1:n;
            ma.push(i);
            mi.push(i);
        }
        LL ans1=0, ans2=0;
        for(int i=1;i<=n;i++){
            ans1+=(LL)data[i]*(i-mal[i]+1)*(mar[i]-i+1);
            ans2+=(LL)data[i]*(i-mil[i]+1)*(mir[i]-i+1);
            //printf("%d %d %d %d\n",mil[i],mir[i],mal[i],mar[i]);
        }
        printf("%lld\n", ans1-ans2);
    }
    return 0;
}