題目大意: 給定一個長度為n的循環序列，從n個不同位置開始，問有幾個位置使得一下情況成立:所有前綴的和都大等於0(n <=100萬).
解題思路:下午做的swerc的G題，這題想成線段樹敲了十多分鐘，然後TLE了，爾後就去敲第一題Polya，拿了個FB。
線段樹之所以會T，是因為它的復雜度是O(nlogn)，這樣n等於100萬的時候大概要操作8千萬左右，而用單調隊列只要O(n)，操作數大概為2百萬，結果線段樹T了，單調隊列過了。
之所以會想到線段樹來做這題是因為順著出題者的思路，模擬題目的n次循環操作，每次成段更新成段查詢最小值就好，非常好想非常好寫。這樣的話就被出題者束縛住思路了，很多時候往往就是因為思路被束縛了，所以應該出的題目沒有出。
這題要求說所有的前綴和大等於0，如果前面一個滾到最後，看似要更新，其實完全不要更新，只要用0加上sum[i]表示前i個數的和，這個值稱為Minval，我們要做的是維護這個Minval，並計算從i位到i+n-1位所有前綴的最小sum[i]，記為Minsum,如果Minsum >= Minval就合法答案加1.這個Minval其實就是前綴i的總和(1<=i<=n).
然後就是求固定區間長度的最小值，這個用單調隊列最合適了。做完此題好好思考了下，對於區間查詢，線段樹應該是首選，但是當限制條件條件增加時應該選擇更簡潔效率更高的數據結構完成操作，對於本題，限制條件是區間固定，而且數組不動態變化，變化的是Minval，那麼用單調隊列更優。
基於以上的分析，剩下的就是編碼，最近似乎稱為碼農了，每場比賽都是我一個人在敲，不比賽時一題經常會敲很多遍。
測試數據:
4
3 -1 -1 1
3
-1 1 1
3
1 2 3
C艹代碼:
[cpp]
#include <stdio.h>
#include <string.h>
#define MAX 2100000
struct node {
int sum,id;
}qu[MAX];
int n,head,tail,ans;
int sum[MAX],arr[MAX];
int main()
{
int i,j,k;
while (scanf("%d",&n) != EOF) {
if (n == 0) break;
ans = head = tail = 0;
for (i = 1; i <= n; ++i) {
scanf("%d",&arr[i]);
sum[i] = sum[i-1] + arr[i];
}
for (i = 1; i <= n; ++i)
sum[i+n] = sum[i+n-1] + arr[i];
for (i = 1; i <= 2 * n; ++i) {
while (tail < head && sum[i] < qu[head-1].sum)
head--;
qu[head].sum = sum[i],qu[head].id = i,head++;
if (i > n && qu[tail].sum >= sum[i-n]) ans++;
while (tail < head && qu[tail].id <= i - n + 1) tail++;
}
printf("%d\n",ans);
}
}
