CodeCraft-22 and Codeforces Round #795 (Div. 2) D. Max GEQ Sum

题目链接

给出一个序列 a a a，判断整个序列中是否所有的区间都满足区间最大值大于等于区间和

单调栈找到每个 i i i 左右比 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]) 的最大子区间，判断是否符合条件即可。找最大最小值 s t st st 表足够

#include
#define LL long long
#define pb push_back
using 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];
vectorpos;
LL findmx(int L,int R)
{
	LL temp=-1e18-7;
	for(int i=20;i>=0;i--)
		if(L+(1<
	LL temp=1e18+7;
	for(int i=20;i>=0;i--)
		if(L+(1<
	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<
			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?"NOn":"YESn");
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}