建站图标素材,网站开发语言市场有率,上海企业网络推广公司,计算机网络 网站也是不知道为什么突然又复习到单调栈了#xff0c;所以顺手刷了三道题#xff0c;总结一下
P6503 [COCI2010-2011#3] DIFERENCIJA 思路#xff1a;这题是要求每个子区间里面的最大值和最小值的差#xff0c;我们一开始想的必然是纯暴力呀#xff0c;但是一看这数据#…也是不知道为什么突然又复习到单调栈了所以顺手刷了三道题总结一下
P6503 [COCI2010-2011#3] DIFERENCIJA 思路这题是要求每个子区间里面的最大值和最小值的差我们一开始想的必然是纯暴力呀但是一看这数据嚯O(n^2)的时间复杂度这不直接炸了因此我们需要想一个O(n)的算法或者O(nlogn)的算法
我们再次分析题意我们是否可以将题目转换一下变成先求所有区间的最大值然后再一起减去所有区间的最小值然后就变成了求区间最值问题那么就可以用单调栈了时间复杂度为O(n)
我们用四个数组分别存储每个点的左边第一个比他大的右边第一个比他大的左边第一个比他小的右边第一个比他小的然后求最大值就是每个最值只会出现( i - L)*(R - i )次
来看代码
#includebits/stdc.h
using namespace std;
#define int long long
int n;
int a[300005];
int lmin[300005],rmin[300005],lmax[300005],rmax[300005];
stackint q;
void ini()
{while(!q.empty())q.pop();
}
signed main()
{cinn;for(int i1;in;i){cina[i];}for(int i1;in;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 i1;in;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 in;i0;i--){while(!q.empty()a[q.top()]a[i]){q.pop();}if(q.empty()){rmax[i]n1;}else{rmax[i]q.top();}q.push(i);}ini();for(int in;i0;i--){while(!q.empty()a[q.top()]a[i]){q.pop();}if(q.empty()){rmin[i]n1;}else{rmin[i]q.top();}q.push(i);}int ans0;for(int i1;in;i){ansa[i]*(i-lmax[i])*(rmax[i]-i);ans-a[i]*(i-lmin[i])*(rmin[i]-i);}coutans;return 0;
} P1823 [COI2007] Patrik 音乐会的等待 思路这是一个队列但是我们要将其拆成一个链也就是一开始的输入输入进来一个就放一个进栈里面我们要维护的是一个单调递增队列每次进栈的时候也就是相邻的只要栈不为空都要统计数1然后就是如果存在栈弹出也就说明ans但是有可能会出现等高的所以我们还需要统计等高的人数所以栈里面放的是pair数据first用来存高度second用来统计目前已经出现了多少个等高的
#includebits/stdc.h
using namespace std;
#define int long longint n;
int h[500005];
pairint,int p;
stack pairint,int q;
int ans0;
signed main()
{cinn;for(int i1;in;i){cinh[i];}for(int i1;in;i){pmake_pair(h[i],1);while(!q.empty()q.top().firsth[i]){if(q.top().firsth[i]){p.secondq.top().second;}ansq.top().second;q.pop();}if(!q.empty())ans;q.push(p);}coutans;return 0;
}
Bindian Signalizing 思路乍一看和上面的那个一样但是有一个特判就说第一座山有可能会通过反着来看看到后面的山所以需要加上特判
#includecstdio
#includestack
using namespace std;int n;
int a[1000005];
int b[1000005];
int l[1000005];
int r[1000005];
int cnt[1000005];
stackintq;
int main()
{int maxn0,flag0;scanf(%d,n);for(int i0;in;i){scanf(%d,a[i]);if(a[i]maxn){maxna[i];flagi;}}for(int i0;in;i){b[i]a[(flagi)%n];}for(int i1;in;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 in-1;i0;i--){while(!q.empty()b[q.top()]b[i]){q.pop();}if(q.empty())r[i]n;elser[i]q.top();if(r[i]nb[i]b[r[i]]){cnt[i]cnt[r[i]]1;r[i]r[r[i]];}q.push(i);}long long ans0;for(int i0;in;i){anscnt[i];if(b[i]b[0]){ans2;if(l[i]0r[i]n){ans--;}}}printf(%lld\n,ans);return 0;
}
