【题解】P2629

P2629

题目

题目描述：

Uim 在公司里面当秘书，现在有 $n$ 条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条消息的好坏度。最开始老板的心情是 $0$，一旦老板心情到了 $0$ 以下就会勃然大怒，炒了 Uim 的鱿鱼。

Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望知道如何才能不让老板发怒。

Uim 可以使用一种叫 “倒叙” 的手法，例如有 $n$ 条消息，Uim 可以任取一个整数 $k$（$1 \leq k \leq n$），先从 $k$ 事件通报到 $n$ 事件，再从 $1$ 事件通报到 $k-1$ 事件。特别的，当 $k=1$ 时按照原顺序通报。

他希望知道，有多少个这样的 $k$ 可以让老板不发怒。

输入格式：

第一行一个整数 $n$（$1 \le n \le10^6$），表示有 $n$ 个消息。

第二行 $n$ 个整数，按时间顺序给出第 $i$ 条消息的好坏度 $A_i$（$-10^3\le A_i \le 10^3$）。

输出格式：

一行一个整数，表示可行的方案个数。

数据范围与说明：

【样例解释】

通报事件的可行顺序（用编号表示）为 $2\rightarrow3\rightarrow4\rightarrow1$ 或 $3\rightarrow4\rightarrow1\rightarrow2$（分别对应 $k=2$ 和 $k=3$）

通报事件的可行顺序（用好坏度表示）为 $5\rightarrow1\rightarrow2\rightarrow(-3)$ 或 $1\rightarrow2\rightarrow(-3)\rightarrow5$

【数据范围】

对于 $25\%$ 的数据，$n\le10^3$；
对于 $75\%$ 的数据，$n\le10^4$；
对于 $100\%$ 的数据，$1 \le n\le 10^6$。

输入输出样例 #1

输入：

4
-3 5 1 2

输出：

2

代码

#include <bits/stdc++.h>
using namespace std;
long long q[20000006],a[2000006],s[2000006];
int main(){
    int n,l=1,r=0,ans=0;
    scanf("%d",&n);
    for(register int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(register int i=1;i<=n-1;i++){
        a[i+n]=a[i];
    }
    for(register int i=1;i<=2*n-1;i++){
        s[i]=s[i-1]+a[i];
    }
    for(register int i=1;i<=2*n-1;i++){
        while(l<=r&&max(i-n+1,1)>q[l]){
            l++;
        }
        while(l<=r&&s[q[r]]>=s[i]){
            r--;
        }
        q[++r]=i;
        if(i-n+1>0&&s[q[l]]-s[i-n]>=0){
            ans++;
        }
    }
    printf("%d\n",ans);
}