题目链接
题意
给出一个序列 aaa，判断整个序列中是否所有的区间都满足区间最大值大于等于区间和
题解
单调栈找到每个 iii 左右比 a[i]a[i]a[i] 大的第一个数的位置 l[i],r[i]l[i],r[i]l[i],r[i]，那么在区间 (l[i],r[i])(l[i],r[i])(l[i],r[i]) 最大值为 a[i]a[i]a[i]，只需要找到 [i,r[i]−1][i,r[i]-1][i,r[i]−1] 的最大值和 [l[i],i−1][l[i],i-1][l[i],i−1] 的最小值，它们的差就是区间 (l[i],r[i])(l[i],r[i])(l[i],r[i]) 的最大子区间，判断是否符合条件即可。找最大最小值 ststst 表足够
代码
#include<bits/stdc++.h>#define LL long long#define pb push_backusing namespace std;const int N=2e5+9,M=29;int T,n;int l[N],r[N];LL a[N],sum[N],mx[N][M],mn[N][M];vector<int>pos;LL findmx(int L,int R){LL temp=-1e18-7;for(int i=20;i>=0;i--)if(L+(1<<i)-1<=R)temp=max(temp,mx[L][i]),L+=(1<<i);return temp;}LL findmn(int L,int R){LL temp=1e18+7;for(int i=20;i>=0;i--)if(L+(1<<i)-1<=R)temp=min(temp,mn[L][i]),L+=(1<<i);return temp;}void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];mx[i][0]=mn[i][0]=sum[i];}mx[0][0]=mn[0][0]=0;for(int j=1;j<=20;j++)for(int i=0;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);}pos.clear();a[0]=1e9+7; pos.pb(0);for(int i=1;i<=n;i++){while(a[i]>=a[pos.back()]) pos.pop_back();l[i]=pos.back();pos.pb(i);}pos.clear();a[n+1]=1e9+7; pos.pb(n+1);for(int i=n;i>=1;i--){while(a[i]>=a[pos.back()]) pos.pop_back();r[i]=pos.back();pos.pb(i);}int flag=0;for(int i=1;i<=n&&!flag;i++)if(findmx(i,r[i]-1)-findmn(l[i],i-1)>a[i])flag=1;cout<<(flag?"NO\n":"YES\n");}int main(){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin>>T;while(T--) solve();return 0;}
