【51nod 1215】数组的宽度

N个整数组成的数组，定义子数组a[i]…a[j]的宽度为：max(a[i]…a[j]) - min(a[i]…a[j])，求所有子数组的宽度和。
思路：
维护两个单调栈，累加最大值*最大值覆盖的区间长度maxsum 和 最小值与最小值福海区间长度minsum maxsum-minsum就是答案
代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=50010;
typedef long long ll;
int a1[maxn],a2[maxn];
int maxid[maxn],minid[maxn];
int id1,id2;
int n;
ll maxx,minn;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a1+i),a2[i]=a1[i];
    n++;
    a1[n]=0x7fffffff,a2[n]=-1;
    for(int i=1;i<=n;i++){
        while(id1&&a1[i]>=a1[maxid[id1]]) maxx+=1LL*a1[maxid[id1]]*ll(i-maxid[id1])*(maxid[id1]-maxid[id1-1]),id1--;
        while(id2&&a2[i]<=a2[minid[id2]]) minn+=1LL*a2[minid[id2]]*ll(i-minid[id2])*(minid[id2]-minid[id2-1]),id2--;
        minid[++id2]=maxid[++id1]=i;
        }
    printf("%lld",maxx-minn);
}