官方题解

题目大意

有一个长度为 $n$ 的数组 $a$ ，判断是否所有区间 $[i,j]$ 满足 $max(a_i,a_{i+1},\dots,a_{j-1},a_j)\geq a_i+a_{i+1}+\dots +a_{j-1}+a_j$ 。

解题思路

我们考虑对于每一个位置 $i$ ，如果这个位置的数是区间最大值，首先找出所有满足这个数为最大值的区间，这部分我们可以用单调栈求出左边和右边第一个大于这个数的位置 $L_i$ 和 $R_i$ ，时间复杂度是 $O(n)$ 线性的。

然后对于每一个位置 $i$ ，在区间 $[L_i,R_i]$ 中，如果最大的区间和比这个数还要小的话，那么这个位置就是满足条件的。在找最大区间和时，需要注意，由于位置 $i$ 一定需要在区间中，所以我们需要在 $[i,R_i-1]$ 中找到最大前缀和 $mxs$ ，在 $[L_i,i-1]$ 中找到最小前缀和 $mis$ ，区间 $[L_i,R_i]$ 中的最大区间和就是 $mxs-mis$ 。

可以用 $st$ 表或者线段树快速查询区间最大最小前缀和。

时间复杂度 $O(nlogn)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
const int N = 200010;

int lg[N];

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    vector<int>l(n+1),r(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        l[i]=0;
        r[i]=n+1;
    }
    stack<PII>stk;
    for(int i=1;i<=n;i++){
        while(!stk.empty() && stk.top().second<a[i]){
            r[stk.top().first]=i;
            stk.pop();
        }
        stk.push({i,a[i]});
    }
    while(!stk.empty()) stk.pop();
    for(int i=n;i>=1;i--){
        while(!stk.empty() && stk.top().second<a[i]){
            l[stk.top().first]=i;
            stk.pop();
        }
        stk.push({i,a[i]});
    }

    vector<int>s(n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

    vector<vector<int>>mx(31,vector<int>(n+1)),mi(31,vector<int>(n+1));
    for(int i=0;i<=n;i++) mx[0][i]=mi[0][i]=s[i];
    for(int j=1;j<=30;j++){
        for(int i=0;i+(1ll<<(j-1))<=n;i++){
            mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1ll<<(j-1))]);
            mi[j][i]=min(mi[j-1][i],mi[j-1][i+(1ll<<(j-1))]);
        }
    }

    auto querymx=[&](int l,int r)->int {
        int k=lg[r-l+1];
        return max(mx[k][l],mx[k][r-(1<<k)+1]);
    };
    auto querymi=[&](int l,int r)->int {
        int k=lg[r-l+1];
        return min(mi[k][l],mi[k][r-(1<<k)+1]);
    };
    
    for(int i=1;i<=n;i++){
        int MI=querymi(l[i],i-1);
        int MX=querymx(i,r[i]-1);
        if(MX-MI>a[i]){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(int i=2;i<=N-10;i++) lg[i]=lg[i>>1]+1;
    
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}