[数据结构与算法][cf] 795 div2 D. Max GEQ Sum

前言

$tag:$ 单调栈 所有子区间 数据结构 线段树
传送门 :

题意 :
给定给一个数组$a[]$,询问是否满足

${?}_{i}max(a_i,a_i+1...a_{j?1},a_j)\ge a_i+a_{i+1}+...a_{j?1}+a_j$

数据范围 :
$t:1e5,n:2e5$

思路 :

显然的,我们并不能直接$n^2$的进行枚举区间

但是我们可以知道的是$max(a[l,r])$

我们设$a[x]$是上式求出来的值,那么他所能覆盖的区间必然是固定的即$L[x],R[x]$

$L[x]$表示左边大于$a[x]$的第一个数的下标
$R[x]$表示右边大于$a[x]$的第一个数的下标

这样子我们就可以求出来$a[x]$所服务的区间
即$[L[x]+1,R[x]?1]$

因此对于题中的式子我们就可以简化为
$a[x]\ge max(sum[r]?sum[l?1])$

即最大化$L[x],R[x]$里面的区间和,判断是否可行

十年$cf$一场空,不开$ll$见祖宗
因为对自己的线段树和单调栈不够自信,$wa2$之后一直在看自己的代码到底是不是有漏洞

$QAQ$完全没注意到$LL$

code :

const int N = 2e5+10;
const ll INF =  1e18;

const double eps = 1e-5;

struct node{
	int l,r;
	ll minv;
	ll maxv;                  
}tr[N*4];
int n;

ll pre[N];
ll L[N],R[N];
ll a[N];

void pushup(int u){
	tr[u].maxv = max(tr[u<<1].maxv,tr[u<<1|1].maxv);
	tr[u].minv = min(tr[u<<1].minv,tr[u<<1|1].minv);
}

void build(int u,int l,int r){
	if(l == r){
		tr[u] = {l,r,pre[l],pre[l]};
		return;
	}
	
	tr[u] = {l,r,INF,-INF};
	int mid =(l+r)>>1;
	
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

ll query_MIN(int u,int l,int r){
	if(tr[u].l >= l && tr[u].r<=r)
    return tr[u].minv;

    int mid = (tr[u].l+tr[u].r)>>1;
    ll v = INF;
    if(l<=mid) v = min(v,query_MIN(u<<1,l,r));
    if(r>mid)  v=  min(v,query_MIN(u<<1|1,l,r));
    return v;
	
}
ll query_MAX(int u,int l,int r){
	if(tr[u].l >= l && tr[u].r<=r)
        return tr[u].maxv;

    int mid = (tr[u].l+tr[u].r)>>1;
    ll v = -INF;
    if(l<=mid) v = max(v,query_MAX(u<<1,l,r));
    if(r>mid)  v=  max(v,query_MAX(u<<1|1,l,r));
    return v;
}


void solve(){
	cin>>n;
	
	stack<int> stk;
	
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		L[i] = 0 ;
		R[i] = 0;
	}
	a[n+1] = INF;
	
	for(int i=1;i<=n+1;i++){
		while(stk.size() && a[stk.top()]<a[i]){
			R[stk.top()] = i;
			stk.pop();
		}
		stk.push(i);
	}
	
	while(stk.size()) stk.pop();
	a[0] = INF;
	
	for(int i=n;i>=0;i -- ){
		while(stk.size() && a[stk.top()]<a[i]){
			L[stk.top()] = i ;
			stk.pop();
		}
		stk.push(i);
	}
	
	for(int i=1;i<=n;i++)
	pre[i] = pre[i-1]+a[i];
	
	build(1,0,n);
	
	for(int i=1;i<=n;i++){
		if(a[i] < query_MAX(1,i,R[i]-1) - query_MIN(1,L[i],i-1)){
			cout<<"NO"<<endl;
			return;
		}
	}
	cout<<"YES"<<endl;
	
}

int main(){
    int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系