https://www.luogu.org/problemnew/show/P2629
题目中文的，不说了；
做法：这道题就不是裸的单调队列了，这道题因为是一个环首先把他，连在一起，然后求一个前缀和sum;
对于每一个点k如果满足题目要求，则在sum[k]到sum[k+n-1]，这个范围内，最小值减去sum[k-1]应该是大于0的
所以就可以用单调栈维护了，当然线段树哪些也可以；
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=2e6+10; int n,m,a[N],sum[N]; int que[N],head,tail,id[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i]; sum[0]=0; for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; int ans=0; head=1,tail=0; for(int i=1;i<n;i++) { while(head<=tail&&que[tail]>=sum[i]) tail--; que[++tail]=sum[i],id[tail]=i; } for(int i=n;i<2*n;i++) { while(head<=tail&&que[tail]>=sum[i]) tail--; que[++tail]=sum[i],id[tail]=i; while(id[head]<i-n+1) head++; if(que[head]-sum[i-n]>=0) ans++; } cout<<ans<<endl; return 0; }
