怎么看个人做的付费视频网站/英文网站推广

题目链接：https://ac.nowcoder.com/acm/problem/20806
来源：牛客网
​
题意：求所有区间的最大值减最小值的和。

题记：由题意分析可分解成先求出所有区间的最大值的和，再减去所有区间最小值的和。
那么用单调栈取维护以a[i]为区间的最大值往左右两边找比a[i]小的值。l[i]表示可以向左扩展到这个点，r[i]同理。那么以a[i]为最大值的区间有两种情况
1、以a[i]为区间的端点：可以在r[i到l[i]中任意选一点为另一个端点。
2、a[i]为区间中的一点，可以在l[i]到i和i到r[i]中选左端点和右端点。

最后求最小值得和可以把a[i]全部加上一个负号重复以上操作即可。

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N],l[N],r[N];
int n;ll 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>0;i--){int j=i;while(j<n&&a[j+1]<a[i])j=r[j+1];r[i]=j;}ll 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;
}int main(){int T;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];ll ans1=solve();for(int i=1;i<=n;i++)a[i]=-a[i];ll ans2=solve();cout<<ans1+ans2<<endl;}return 0;
}