题意：一个数列，求分别以每个元素为首位时（循环），前缀和都非负的序列个数

分析：

首先是个循环序列问题，所以要做处理：把序列复制一遍变成2*n的序列，这样任意一个长度为n的区间就是一种序列，共n种

然后求前缀和就可以用sum[j]-sum[i-1]，这个式子表示以第i的元素为首位的序列，然后以第j个元素结尾的前缀和。同一个序列的不同结尾的前缀和每次都是减sum[i-1]，只有sum[j]不同，所以我们就求出sum[j]中最小的再减去sum[i-1]看是否小于0即可。sum[]很好求，O(2*n)就求出来了，因此我们现在就是要求一个长度为n的区间里面sum[j]的最小值，也就是一个移动的固定区间求最值，用单调队列O(n)解决。

另外cin，cout又TLE了，弃用....

代码：

?

#include
  
   
#include
   
     using namespace std; int head,rear; int a[2000010]; int q[1000010]; int n; void pushq(int i) { while(head<=rear&&a[q[rear]]>=a[i]) rear--; q[++rear]=i; } void popq(int i) { while(q[head]
    
     =0) tot++; } printf(%d ,tot); } }
    
   
  

?

?