描述:https://www.luogu.com.cn/problem/P2629
uim在公司里面当秘书，现在有n条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于之前老板的心情加上这条消息的好坏度。最开始老板的心情是0，一旦老板心情到了0以下就会勃然大怒，炒了uim的鱿鱼。
uim为了不被炒，知道了了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望研究如何不让老板发怒。
uim必须按照时间的发生顺序逐条将消息告知给老板。不过uim可以使用一种叫“倒叙”的手法，例如有n条消息，小a可以从k,k+1,k+2...n,1,2...k-1这种顺序通报。
他希望知道，有多少个k，从k开始通报到n然后从1通报到k-1可以让老板不发怒。
又是比较难想的一题，虽然这已经是第二次做了........
首先区间牵涉到k~n,n~1，那么大概率是要断环为链的。
断环为链后，题目要求就变为了：对于每一个合法的k，都要满足k--(n+k-1)中，到任意一点的和都是非负的。熟悉前缀和的人应该知道，如果用 s [ i ] 表示1--i的所有数的和，那么s [ j ] - s [ i-1 ] 就是i--j所有数的和。所以用前缀和预处理后，s [ i ] - s [ k-1 ] 就是k--i (k<=i<=n+k-1)的和了，我们只要判断这个和是否为负即可。
既然这么说，那么是否要判断k--n+k-1中每一个数的和呢？当然不是，因为其中如果只要有一点的和是负的，那么这个k就是不合法的了，所以我们只需要判断一次——判断最小的si减去s[k-1]是否为负。
接下来就是单调队列的事了。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,p[2000009],q[2000009]; ll a[2000009],sumn[2000009],he[2000009]; int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sumn[i]=sumn[i-1]+a[i]; for(int i=n+1;i<=n+n;i++) a[i]=a[i-n],sumn[i]=sumn[i-1]+a[i]; int tail=0,head=1,l=n-1; for(int i=1;i<=n+n;i++) { while(tail>=head&&q[tail]>=sumn[i]) tail--; q[++tail]=sumn[i],p[tail]=i; while(p[head]+l<=i) head++; if(i>=n) he[i-l]=q[head];//区间长度为n-1,所以从n开始记录 } int ans=0; for(int i=1;i<=n;i++) if(he[i]-sumn[i]>=0) ans++; cout<<ans; }