[数据结构与算法][cf] Codeforces 817D Imbalanced Array 单调栈

前言

传送门 :

优质题解传送门 :

wls题目传送门 :

思路

使用单调栈维护当前节点 是最大值的时候的区间

以及当前节点是最小值时候的区间

然后统计计数即可

而求区间最大最小值可以使用单调栈处理

MyCode

//��?��?�??�� ��??��#define int long long TLE���?��???�?�� ���?���?��
//����?�?��?�?��

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define int long long
#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()


typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;

const int N  = 5e5+10;
int a[N],n;
int l[N],r[N];

stack<int> stk;
int ans = 0 ;

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int i=1;i<=n;i++){
		// 队列不空 并且当前元素大于要入栈元素
		while(!stk.empty() && a[stk.top()] >=a[i]) stk.pop();
		if(stk.empty()) l[i] =  i - 1;
		else  l[i] =  i - stk.top() - 1;
		stk.push(i);
	}
	while(!stk.empty()) stk.pop();
	
	for(int i = n ;i >= 1;i -- ){
		while(!stk.empty() && a[stk.top()] > a[i]) stk.pop();
		if(stk.empty()) r[i] = n - i;
		else r[i] = stk.top() - i - 1;
		stk.push(i);

 	}
	
		
	for(int i=1;i<=n;i++){
		ans -= a[i]*(l[i]+1) * (r[i]+1);
		
	}
 	
 	while(!stk.empty()) stk.pop();
 	for(int i=1;i<=n;i++){
 		while(!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
 		if(stk.empty()) l[i] = i -1;
 		else l[i] = i - stk.top() - 1;
 		stk.push(i);
 	}
 	
 	while(!stk.empty()) stk.pop();
 	for(int i=n;i>=1;i  -- ){
 		while(!stk.empty() && a[stk.top()] < a[i]) stk.pop();
 		if(stk.empty())  r[i] = n-i ;
 		else r[i] = stk.top() - i - 1;
 		stk.push(i);
 	}
 	
 	for(int i=1;i<=n;i++)
 	ans += a[i]*(l[i] +1 ) * (r[i]+1);
 	cout<<ans<<endl;
 	
 	
	
	
}
/**mYHeart is my algorithm**/
signed main()
{
    //int t;cin>>t;while(t -- )
    solve();
    return 0;
}