正題

題目鏈接:https://www.luogu.com.cn/problem/CF5E

---

題目大意

圓上有$n$個山，兩個山之間可以看到當(dāng)且僅當(dāng)它們之間的兩條弧中有一條滿足所有山都不高于它們兩個。

求可以看到的山的對數(shù)。

$3\le n\le 10^6,1\le h_i\le 10^9$

---

解題思路

先找到最高的山，然后先考慮它之外的點對再考慮這座山的貢獻(xiàn)，因為這樣矮的點之間肯定有一座高山擋著。

然后前后各維護(hù)一個單調(diào)隊列，每個元素被彈出的時候就會統(tǒng)計一個點對。

然后考慮相同的情況，對于前后中的一個做的時候，彈完之后在單調(diào)隊列上二分相同的位置即可。

時間復(fù)雜度$O(n\log 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\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF5E-Bindian Signalizing【单调栈】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。