HDU 4193 Non

題意：一個數列，求分別以每個元素為首位時（循環），前綴和都非負的序列個數

分析：

首先是個循環序列問題，所以要做處理：把序列復制一遍變成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);
	}
}