Codeforces Round #795 (Div. 2)D

D题链接
题意：给定数组a，询问是否对于所有的i小于j都有：max(ai,ai+1,…,aj)>=ai+…+aj.
思路：如果我们直接枚举i，j的话时间复杂度是n^2,那么我们就换个思路，我们可以把这个问题转化成在一个点a[i]点上寻找其为最值的区间上和最大，那么我们就可以在i的点向左向右找最近的大于a[i]的下标，并把其记录下来标记为l和r（这里我们可以用单调栈去处理），那么最大值我们确定了，那区间和最大值应该怎么求呢，我们可以先用前缀和预处理一下，然后然后在l+1到i直接找到一个最小前缀，在i到r直接找到一个最大前缀（这里可以用线段树也能用ST表，这里用的是ST表）然后我们就可以判断了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> struct ST{
    ST(T a[], int n){
        siz = n;
        maxv.resize(n+1); minv.resize(n+1);
        int t = __lg(n) + 1;
        for(int i= 0;i<=n;i++) maxv[i].resize(t), minv[i].resize(t);
        for(int i = 0; i <= n; i++) maxv[i][0] = minv[i][0] = a[i];
        for(int j = 1; j < t; j++)
        {
            for(int i = 0; i <= n - (1<<j)+1; i++)
            {
                maxv[i][j] = max(maxv[i][j-1], maxv[i+(1 << (j-1))][j-1]);
                minv[i][j] = min(minv[i][j-1], minv[i+(1 << (j-1))][j-1]);
            }
        }
    }
    T getmax(int l,int r){
        int k = __lg(r-l+1);
        return max(maxv[l][k],maxv[r-(1<<k)+1][k]);
    }
    T getmin(int l,int r){
        int k = __lg(r-l+1);
        return min(minv[l][k],minv[r-(1<<k)+1][k]);
    }
private:
    int siz = 0;
    vector<vector<T>> maxv, minv;
};

void solve()
{
    int n; cin>>n;
    vector left(n+1, 0), right(n+1, n+1);
    ll a[n+1]; for(int i=1;i<=n;i++) cin>>a[i];
    stack<array<ll, 2>> st;
    for(int i=1;i<=n;i++)
    {
        while(!st.empty() && st.top()[1] < a[i]) right[st.top()[0]] = i, st.pop();
        st.push({i, a[i]});
    }

    while(!st.empty()) st.pop();

    for(int i=n;i>=1;i--)
    {
        while(!st.empty() && st.top()[1] < a[i]) left[st.top()[0]] = i, st.pop();
        st.push({i, a[i]});
    }

    ll pre[n+1]; pre[0] = 0;
    partial_sum(a+1, a+1+n, pre+1);
    ST<ll> s(pre, n);

    for(int i=1;i<=n;i++)
    {
        ll p1 = s.getmin(left[i], i-1), p2 = s.getmax(i, right[i] - 1);
        if(p2 - p1 > a[i]) {cout<<"NO\n"; return;}
    }
    cout<<"YES\n";
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }


}