题目描述:
众所周知，如今的波兰在很久以前住着很多部落。他们的首都被n座山所环绕，形成一个圆圈。在每一座山上有一个哨兵，他日夜观察附近的山。
如果有任何危险，哨兵会在山上放一把火。如果在连接两座山的圆弧上的任何一座山都不高于这两座山，那么这两座山上的哨兵能相互看到对方。由于任意两座山都有两条不同的圆弧连接他们，所以如果这两条圆弧中的任意一条能满足以上条件，那么信号就可见。例如，对于任意两个相邻的哨兵，他们的信号都是互相可见的。
一个侦查系统的重要特征是能看见对方信号的哨兵的对数。你需要根据给出的山的高度得到这些哨兵的对数。
解题报告:
10WA,用时1h50min
这题做的不是很好，开始我普通的破环成链，写了一个单调队列，然后在其中二分大于当前值的最小值的位置t，然后对答案贡献就是(r-t+1),最后发现是有问题的，因为当两个点可以从两边看到时，那么就会统计两次
然后请教大佬，处理重复的方式是去掉序列中最大值，然后把最大值前一段接在后一段，再按我的做法做一遍，然后再统计最大值贡献即可，为什么是对的？
因为答案不可能穿过最大值的位置，除非两边的都等于最大值，既然都等于最大值，那么无论正向反向都可以被统计到,然后就非常简单了.
注意:在统计最大值的贡献时细节很多，本蒟蒻在这里WA了很久..
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=2e6+5;
int n,a[N],l=1,r=0,q[N],val=0,b[N],tot=0;
int gi(){
int str=0;char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
int midit(int x){
int L=l,R=r,mid,ret=l;
while(L<=R){
mid=(L+R)>>1;
if(q[mid]>x)ret=mid,L=mid+1;
else R=mid-1;
}
return ret;
}
int c[N];bool d[N];
void work()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
a[i]=gi();c[i]=a[i];c[i+n]=c[i];
if(a[i]>a[val])val=i;
}
for(int i=val+1;i<=n;i++)
b[++tot]=a[i];
for(int i=1;i<val;i++)
b[++tot]=a[i];
n--;
for(int i=1;i<=n;i++)a[i]=b[i];
int t;ll ans=0;
for(int i=1;i<=n;i++){
if(l<=r){
t=midit(a[i]);
ans+=r-t+1;
}
while(l<=r && a[i]>q[r])r--;
q[++r]=a[i];
}
int mx=0,lim=val+n;n++;
for(int i=val+1;i<=lim;i++){
if((c[i]>=mx && mx<=c[val]) || (i==val+1)){
if(i>n)d[i-n]=true;
else d[i]=true;
mx=c[i];
}
}
mx=0;
for(int i=lim;i>=val+1;i--){
if((c[i]>=mx && mx<=c[val]) || (i==val-1)){
if(i>n)d[i-n]=true;
else d[i]=true;
mx=c[i];
}
}
for(int i=1;i<=n;i++)ans+=d[i];
printf("%lld
",ans);
}
int main()
{
work();
return 0;
}