CF5E Bindian Signalizing

题目

CF5E Bindian Signalizing

分析

单调栈(+dp) 。

首先我们要把环处理成链，这道题因为特性我们可以直接把最高的山选成第一个就好了。

然后可以使用单调栈，维护一个单调递减的单调栈，更新答案就是相当于当前这个点之前所有比这个点小的都由这个点更新，完了放进栈里面，注意判断相等。

放进栈里面就是把这个作为 (l) ，然后由另外的 (r) 来更新它。

代码

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=2e6+5,V=5e5;
int n,m,a[N],b[N],sta[N],cnt[N],top,Max,pos;
#define ll long long
ll Ans;
signed main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		if(a[i]>Max) Max=a[i],pos=i;
	}
	for(int i=pos+1;i<=n;i++) b[++m]=a[i];
	for(int i=1;i<pos;i++) b[++m]=a[i];
	Ans=n-1;
	for(int i=1;i<=m;i++){
		while(top&&sta[top]<b[i]) Ans+=cnt[top--];
		if(sta[top]!=b[i]) sta[++top]=b[i],cnt[top]=0;
		Ans+=cnt[top]++;
	}
	while(top>1) Ans+=cnt[top--];
	write(Ans);
	return 0;
}

注意

还不怎么会这种类似的单调栈的用法，要多体会。