[cf] Codeforces 817D Imbalanced Array 单调栈

前言

传送门 :

优质题解传送门 :

wls题目传送门 :

思路

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

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

然后统计计数即可

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

MyCode

//��һ�δ��Ϻ�վ֮�� ��Ϊʹ��#define int long long TLE���¿��˺ܾõ�ʱ�� ���˼���ģ��
//����ʹ�ø��ӵ�ģ��

#include 
#include 
#include 
#include 
#include 
#include 
#include 
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  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;

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

stack stk;
int ans = 0 ;

void solve()
{
	cin>>n;
	for(int i=1;i>a[i];
	}
	
	for(int i=1;i=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