Sol.CF1691D

本文同步发布于我的洛谷博客：链接

正文：

赛时大寄，最后十分钟没有调出来，下大分！

题意简述

给你一个正负数都有的序列，试判断是否对于所有的子区间都有区间和大于等于区间最大值成立。

有多组数据。

解法：

考虑怎么样的情况下让这个不等式不成立，那无非是区间最大值去正数，然后让区间和尽量大。

于是不难想到，我们可以对于每一个正数，考虑他作为区间最大值的情况，然后在它可以做最大值的区间内找区间最大和，然后与当前这个正数比较来判断。

区间最大和可以用一个保存了前缀和的线段树来实现查询；一个正数可以做最大值的区间即前一个比他大的数和后一个比他大的数所夹区间（若没有这样的数就去序列的首或尾），寻找这个区间的过程可用单调栈来实现。

具体操作详见代码。

/*
  Author:Lucky_Yukikaze

*/
#include
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define re register
#define pb push_back
#define mp make_pair
#define pf pop_front
#define pob pop_back
#define fr front
#define bk back

using namespace std;
typedef pair pii;
typedef long double ld;
typedef pair pll;

namespace Morgen{

	inline int fr(){
		int res=0;bool sig=false;char tp=getchar();
		while(!isdigit(tp)){
			if(tp=='-')sig=!sig;
			tp=getchar();
		}
		while(isdigit(tp)){
			res=(res<<1)+(res<<3)+tp-'0';
			tp=getchar();
		}
		if(sig)res=-res;
		return res;
	}
	
	int T;
	int n;
	ll a[200010];
	ll qzh[200010];
	int pre[200010],nex[200010];
	struct element{
			ll minn,maxx;
	}dat[800010];
	struct segt{
		
		
		
		void build(int nowa,int l,int r){
			if(l==r){
				dat[nowa].minn=dat[nowa].maxx=qzh[l];return;
			}
			int mid=(l+r)>>1;
			build(nowa<<1,l,mid);
			build(nowa<<1|1,mid+1,r);
			dat[nowa].maxx=max(dat[nowa<<1].maxx,dat[nowa<<1|1].maxx);
			dat[nowa].minn=min(dat[nowa<<1].minn,dat[nowa<<1|1].minn); 
		}
		
		element query(int nowa,int l,int r,int tl,int tr){
			if(tl<=l&&r<=tr)return dat[nowa];
			int mid=(l+r)>>1;
			element res1,res2,res;
			res1=res2=(element){(ll)1e18,(ll)-1e18};
			if(tl<=mid)res1=query(nowa<<1,l,mid,tl,tr);
			if(tr>mid)res2=query(nowa<<1|1,mid+1,r,tl,tr);
			return (element){min(res1.minn,res2.minn),max(res1.maxx,res2.maxx)};
		}
			
	}sg;
	
	void main(){

		cin>>T;
		
		while(T--){
			cin>>n;
			qzh[0]=0;
			for(int i=1;i<=n;i++){
				cin>>a[i];
				qzh[i]=qzh[i-1]+a[i];
			}
			sg.build(1,0,n);
			stack>stk;
			for(int i=1;i<=n;i++){
				if(a[i]>0){
					while((!stk.empty())&&stk.top().first0){
					element qf=sg.query(1,0,n,pre[i],i),hf=sg.query(1,0,n,i,nex[i]);
					ll sm=qzh[i]-qf.minn+hf.maxx-qzh[i];
					if(a[i]