[TIOJ 1841][POI 21 Stage 1]好．傳囉！ Nice Boat！

(題號打錯所以只好重發文章@@，順便套用剛學的latex語法)
因為HOJ在我寫完這題之後的submissions都沒有動靜(聽說HOJ快要壽終正寢了，好難過QAQ)，所以現在來寫TIOJ了XD

這題題目敘述有點雜，還誤會題目意思打錯code，花了不少時間才理解成功@@
就是，給你一個數列，求最長區間的長度，使得這個區間的任意前綴和後綴和都$\geq 0$

首先，區間的任意前綴和後綴和都是區間和，可以用數列的前綴和(不是區間的)相減求得
假設一開始的$0$也算進去的話，我們可以把這些前綴和畫成有$N+1$個點的折線圖

而假設有一個區間符合題目的條件，把它對應到折線圖上面
那麼仔細思考就可以發現，在折線圖的這個區間裡面，區間左端是最低點，右端是最高點，中間不會允許任何一個點突破兩端的極值(不然就會有區間前綴或後綴和$<0$了)

為了方便說明，定義規則1為區間中間的值必須$\leq$右端點，規則2為區間中間的值必須$\geq$左端點
我們可以先預處理出每個左端點$u$符合規則2中最右邊的右端點$R[u]$，可以用單調對列實現。可以證明，在左端點到$R[u]$之間的所有點，都會是符合規則2的右端點
再來，對於每個左端點，可以維護一個符合規則1的右端點的集合，這一樣可以用單調對列從右到左掃實現
這樣，當左端點維護到$u$時，我們就可以在這個集合裡面進行二分搜，在符合規則1的右端點之中找出最大且$\leq R[u]$的點$v$，那麼$[u,v]$就是符合題目要求中左端點是$u$的最長區間了
在這些計算結果中，取最大的區間長度即可

時間複雜度：$O(N\log N)$

code:

#include<cstdio>
#include<vector>
#include<cassert>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
void getmax(int &a,const int b){if(b>a)a=b;}
struct Stack
{
    vector<int>data;
    int last;
    void clear(){data.clear(),last=-1;}
    void push(const int v){data.push_back(v),last++;}
    void pop(){data.pop_back(),last--;}
    int top()const{return data[last];}
    int lower_bound(const int v)
    {
        int l=0,r=last+1;
        while(l<r)
        {
            const int mid=(l+r)/2;
            if(data[mid]>=v)l=mid+1;
            else r=mid;
        }
        assert(r<=last);
        return data[r];
    }
}STK;
int N;
LL SUM[1000002];
int RIGHT[1000001];
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d",&N);
        SUM[0]=0LL;
        for(int i=1;i<=N;i++)scanf("%lld",&SUM[i]),SUM[i]+=SUM[i-1];
        STK.clear();
        SUM[N+1]=-INF,STK.push(N+1);
        for(int i=N;i>=0;i--)
        {
            while(SUM[i]<=SUM[STK.top()])STK.pop();
            RIGHT[i]=STK.top();
            STK.push(i);
        }
        int ans=0;
        STK.clear();
        SUM[N+1]=INF,STK.push(N+1);
        for(int i=N;i>=0;i--)
        {
            while(SUM[i]>SUM[STK.top()])STK.pop();
            STK.push(i);
            getmax(ans,STK.lower_bound(RIGHT[i])-i);
        }
        printf("%d\n",ans);
    }
    return 0;
}