codeforces-817 D. Imbalanced Array(单调栈）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
int n,a[maxn],L[maxn],R[maxn],L1[maxn],R1[maxn];
stack<int>s;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)
	{
		while(!s.empty()&&a[s.top()]>a[i]) s.pop();
		if(s.size()==0) L[i]=1;
		else L[i]=s.top()+1;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=n;i>=1;--i)
	{
		while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
		if(s.size()==0) R[i]=n;
		else R[i]=s.top()-1;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=1;i<=n;++i)
	{
		while(!s.empty()&&a[s.top()]<a[i]) s.pop();
		if(s.size()==0) L1[i]=1;
		else L1[i]=s.top()+1;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=n;i>=1;--i)
	{
		while(!s.empty()&&a[s.top()]<=a[i]) s.pop();
		if(s.size()==0) R1[i]=n;
		else R1[i]=s.top()-1;
		s.push(i);
	}
	ll ans=0;
	for(int i=1;i<=n;++i) 
	ans+=1LL*(i-L1[i]+1)*(R1[i]-i+1)*a[i],
	ans-=1LL*(i-L[i]+1)* (R[i]-i+1)*a[i];
	printf("%lld\n",ans);
}