后来看了07年周泽（大概是？）的论文，才知道原来这个是一个很经典的单调队列题。
题意：给出一个长度为n序列，每次将第一个元素移至最后可以得到有n种序列，问其中有多少个满足对于所以的i（1≤i≤n），sigma(a[k]),(1≤k≤i)>=0，就是可以维护一个递增的序列，这样每次取队首就O(1)的求出是否满足条件了，维护序列只需要O(n)的复杂度。
比赛的时候用dp思想的st（rmq）的O(nlogn)的算法超时了，后来知道原来有一种RMQ转换为LCA，又转化为RMQ的算法可以做，这样复杂度也可要跟单调队列的做法一样，转换为O(n)。
这类单调队列的基本做法吧。
比较习惯的写法：
l=0; r=-1;
for(k=0;k<=n;k++){
while(l<=r&&(没有更优的判断条件，直接带入r计算即可)) r--;
q[++r] = k;
/*if(判断是否有符合题目的解) ans++;（类似的）
while(对于l的边界条件，下一次的l不符合判断条件) l++;*/
或者
while(对于l的边界条件，此次l不符合判断条件) l++;
if(判断是否有符合题目的解) ans++;（类似的）
}
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<map> 7 #define see(x) cout<<#x<<":"<<x<<endl; 8 using namespace std; 9 const int maxn = 1000005; 10 int a[maxn], sum[maxn<<1], que[maxn<<1]; 11 int main(){ 12 int n, i, j, k, s, ans, l, r; 13 while(~scanf("%d",&n)&&n){ 14 scanf("%d",&a[0]); 15 sum[0] = a[0]; 16 for(i=1;i<n;i++){ 17 scanf("%d",&a[i]); 18 sum[i] = sum[i-1]+a[i]; 19 } 20 for(i=n;i<2*n;i++){ 21 sum[i] = sum[i-1]+a[i-n]; 22 } 23 ans = 0; 24 l = r = 0; 25 for(i=0;i<2*n;i++){ 26 while(l<r&&sum[i]<sum[que[r-1]]) r--; 27 que[r++] = i; 28 if(i>=n&&sum[que[l]]-sum[i-n]>=0) ans++; 29 while(l<r&&que[l]<=i-n+1) l++; 30 } 31 printf("%d\n",ans); 32 } 33 return 0; 34 }