求助 急 大大悬关
查看原帖
求助 急 大大悬关
718487
CleverRaccoonʕ•ᴥ•ʔ楼主2023/10/1 15:02
#include <bits/stdc++.h>
using namespace std;
struct node{
	long long lc,rc,tl,tr,val,add;
	node(){lc=rc=add=0;}
}tree[400010];
long long n,m,a[100010],c[100010],op,x,y,k;
void push_down(long long now){
	tree[tree[now].lc].add+=tree[now].add;
	tree[tree[now].rc].add+=tree[now].add;
	tree[tree[now].lc].val+=tree[now].add*(tree[tree[now].lc].tr-tree[tree[now].lc].tl+1);
	tree[tree[now].rc].val+=tree[now].add*(tree[tree[now].rc].tr-tree[tree[now].rc].tl+1);
	tree[now].add=0;
}
void build(long long now,long long l,long long r){
	tree[now].tl=l,tree[now].tr=r;
	if(l==r){
		tree[now].val=a[l];
		return;
	}
	tree[now].lc=now*2,tree[now].rc=now*2+1;
	int mid=(l+r)/2;
	build(tree[now].lc,l,mid);
	build(tree[now].rc,mid+1,r);
	tree[now].val=min(tree[tree[now].lc].val,tree[tree[now].rc].val);
}
void update(long long now,long long l,long long r,long long pos,long long k){
	if(tree[now].tr<l||tree[now].tl>r)return;
	if(tree[now].tl>=l&&tree[now].tr<=r){
		tree[now].val+=(tree[now].tr-tree[now].tl+1)*k;
		tree[now].add+=k;
		return;
	}
	push_down(now);
	if(pos<=(l+r)>>1)
	update(tree[now].lc,l,r,pos,k);
	else
	update(tree[now].rc,l,r,pos,k);
	tree[now].val=min(tree[tree[now].lc].val,tree[tree[now].rc].val);
}
long long query(long long now,long long l,long long r,long long ql,long long qr){
	if(tree[now].tr<l||tree[now].tl>r)return 0;
	if(tree[now].tl>=l&&tree[now].tr<=r)return tree[now].val;
	push_down(now);
	long long res=LLONG_MAX;
	int mid=(l+r)>>1;
	if(ql<=(l+r)>>1)res=min(res,query(tree[now].lc,l,mid,ql,qr));
	if(qr>mid)res=min(res,query(tree[now].rc,mid+1,r,ql,qr));
	return res;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",c+i);
	for(int i=1;i<=n;i++)a[i]=c[i]-c[i-1];
	build(1,1,n+1);
	while(m--){
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld%lld",&x,&y,&k);
			update(1,1,n+1,x,k);
			update(1,1,n+1,y+1,-k);
		}else{
			scanf("%lld%lld",&x,&y);
			puts(query(1,1,n+1,x+1,y)>=0?"Yes":"No");
		}
	}
	return 0;
}
2023/10/1 15:02
加载中...