单调栈（随缘复习到了，顺手刷了）

也是不知道为什么突然又复习到单调栈了，所以顺手刷了三道题，总结一下

P6503 [COCI2010-2011#3] DIFERENCIJA

 

 思路：这题是要求每个子区间里面的最大值和最小值的差，我们一开始想的必然是纯暴力呀，但是一看这数据，嚯！O(n^2)的时间复杂度，这不直接炸了，因此我们需要想一个O(n)的算法或者O(nlogn)的算法

我们再次分析题意，我们是否可以将题目转换一下，变成先求所有区间的最大值，然后再一起减去所有区间的最小值，然后就变成了求区间最值问题，那么就可以用单调栈了，时间复杂度为O(n)

我们用四个数组分别存储每个点的左边第一个比他大的，右边第一个比他大的，左边第一个比他小的，右边第一个比他小的，，然后求最大值就是每个最值只会出现( i - L)*(R - i )次

来看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[300005];
int lmin[300005],rmin[300005],lmax[300005],rmax[300005];
stack<int> q;
void ini()
{while(!q.empty())q.pop();
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){while(!q.empty()&&a[q.top()]<=a[i]){q.pop();}if(q.empty()){lmax[i]=0;}else{lmax[i]=q.top();}q.push(i);}ini();for(int i=1;i<=n;i++){while(!q.empty()&&a[q.top()]>=a[i]){q.pop();}if(q.empty()){lmin[i]=0;}else{lmin[i]=q.top();}q.push(i);}ini();for(int i=n;i>0;i--){while(!q.empty()&&a[q.top()]<a[i]){q.pop();}if(q.empty()){rmax[i]=n+1;}else{rmax[i]=q.top();}q.push(i);}ini();for(int i=n;i>0;i--){while(!q.empty()&&a[q.top()]>a[i]){q.pop();}if(q.empty()){rmin[i]=n+1;}else{rmin[i]=q.top();}q.push(i);}int ans=0;for(int i=1;i<=n;i++){ans+=a[i]*(i-lmax[i])*(rmax[i]-i);ans-=a[i]*(i-lmin[i])*(rmin[i]-i);}cout<<ans;return 0;
}

 P1823 [COI2007] Patrik 音乐会的等待

思路：这是一个队列，但是，我们要将其拆成一个链，也就是一开始的输入，输入进来一个就放一个进栈里面，我们要维护的是一个单调递增队列，每次进栈的时候也就是相邻的，只要栈不为空，都要统计数+1，然后就是如果存在栈弹出，也就说明ans++，但是有可能会出现等高的，所以我们还需要统计等高的人数，所以栈里面放的是pair数据，first用来存高度，second用来统计目前已经出现了多少个等高的

#include<bits/stdc++.h>
using namespace std;
#define int long longint n;
int h[500005];
pair<int,int> p;
stack< pair<int,int> >q;
int ans=0;
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}for(int i=1;i<=n;i++){p=make_pair(h[i],1);while(!q.empty()&&q.top().first<=h[i]){if(q.top().first==h[i]){p.second+=q.top().second;}ans+=q.top().second;q.pop();}if(!q.empty())ans++;q.push(p);}cout<<ans;return 0;
}

Bindian Signalizing

思路：乍一看和上面的那个一样，但是有一个特判，就说第一座山，有可能会通过，反着来看看到后面的山，所以需要加上特判

#include<cstdio>
#include<stack>
using namespace std;int n;
int a[1000005];
int b[1000005];
int l[1000005];
int r[1000005];
int cnt[1000005];
stack<int>q;
int main()
{int maxn=0,flag=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]>maxn){maxn=a[i];flag=i;}}for(int i=0;i<=n;i++){b[i]=a[(flag+i)%n];}for(int i=1;i<=n;i++){while(!q.empty()&&b[q.top()]<=b[i]){q.pop();}if(q.empty())l[i]=0;elsel[i]=q.top();q.push(i);}while(!q.empty())q.pop();for(int i=n-1;i>=0;i--){while(!q.empty()&&b[q.top()]<b[i]){q.pop();}if(q.empty())r[i]=n;elser[i]=q.top();if(r[i]<n&&b[i]==b[r[i]]){cnt[i]=cnt[r[i]]+1;r[i]=r[r[i]];}q.push(i);}long long ans=0;for(int i=0;i<n;i++){ans+=cnt[i];if(b[i]<b[0]){ans+=2;if(l[i]==0&&r[i]==n){ans--;}}}printf("%lld\n",ans);return 0;
}