HDU 4193：循環序列前綴和非負判定與單調隊列優化

問題轉化

給定長度 n 的循環序列，求以每個元素為起點的 n 個循環序列中，前綴和全非負的個數。

核心思路

1. 序列複製：將序列拼接成長度 2n，任意長度 n 區間對應一種循環序列
2. 前綴和：`sum[j] - sum[i-1]` 表示以 i 開頭、以 j 結尾的前綴和
3. 最值判定：同一序列減去固定 `sum[i-1]`，只需檢查區間最小 `sum[j]`
4. 滑動窗口最小值：固定長度 n 區間求最小值 → 單調隊列 O(n)

單調隊列實現

int head = 0, rear = -1;
int q[MAXN];

void pushq(int i) {
    while (head <= rear && a[q[rear]] >= a[i]) rear--;
    q[++rear] = i;
}

void popq(int i) {
    while (q[head] < i - n + 1) head++;
}

int main() {
    // 構建 2n 前綴和數組 a[]
    for (int i = 1; i <= n; i++) {
        pushq(i);
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (a[q[head]] - a[i-1] >= 0) tot++;
        pushq(i + n);
        popq(i + 1);
    }
    printf("%d\n", tot);
}

關鍵細節

• 隊列存下標，值單調遞增
• `popq` 移除滑出窗口的下標
• 輸入輸出用 `scanf/printf` 避免 `cin/cout` TLE