• 周四. 6月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF5E-Bindian Signalizing【单调栈】

admin

11月 28, 2021

正题

题目链接:https://www.luogu.com.cn/problem/CF5E


题目大意

圆上有(n)个山,两个山之间可以看到当且仅当它们之间的两条弧中有一条满足所有山都不高于它们两个。

求可以看到的山的对数。

(3leq nleq 10^6,1leq h_ileq 10^9)


解题思路

先找到最高的山,然后先考虑它之外的点对再考虑这座山的贡献,因为这样矮的点之间肯定有一座高山挡着。

然后前后各维护一个单调队列,每个元素被弹出的时候就会统计一个点对。

然后考虑相同的情况,对于前后中的一个做的时候,弹完之后在单调队列上二分相同的位置即可。

时间复杂度(O(nlog n))


code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n,m,mx,top,a[N],b[N],s[N],v[N];
long long ans;
int main()
{
	scanf("%d",&m);mx=1;
	for(int i=1;i<=m;i++){
		scanf("%d",&b[i]);
		if(b[i]>b[mx])mx=i;
	}
	for(int i=mx+1;i<=m;i++)a[++n]=b[i];
	for(int i=1;i<mx;i++)a[++n]=b[i];
	for(int i=1;i<=n;i++){
		while(top>0&&a[s[top]]<a[i])
			top--,ans++;
		int l=1,r=top;
		while(l<=r){
			int mid=(l+r)>>1;
			if(a[s[mid]]==a[i])r=mid-1;
			else l=mid+1;
		}
		ans+=top-r;
		s[++top]=i;
	}
	top=0;
	for(int i=n;i>=1;i--){
		while(top>0&&a[s[top]]<a[i])
			top--,ans++;
		s[++top]=i;
	}
	for(int i=1,z=0;i<=n;i++)
		if(a[i]>=z)z=a[i],ans+=!v[i],v[i]=1;
	for(int i=n,z=0;i>=1;i--)
		if(a[i]>=z)z=a[i],ans+=!v[i],v[i]=1;
	printf("%lld
",ans);
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。