评测记录

最后一个sub错了一个点

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
int n,k;
LL a[N];

struct qwq{
	int l,r;
	int fr,ls,sum,lazy;
	bool bk;
	
	qwq(){
		l=r=sum=lazy=fr=ls=0ll;
		bk=1;
	}
	
	void color(int x){
		int len=r-l+1;
		sum+=1ll*x*len;
		fr+=1ll*x;
		ls+=1ll*x;
		lazy+=1ll*x;
	}
}t[4*N];
qwq operator+(const qwq &a,const qwq &b){
	if(a.l==0ll) return b;
	if(b.l==0ll) return a;
	qwq c;
	c.l=1ll* a.l, c.r=1ll* b.r;
	c.fr=1ll* a.fr, c.ls=1ll* b.ls;
	c.sum=1ll* a.sum+1ll* b.sum;
	if(a.bk&&b.bk && a.ls<=b.fr) c.bk=1;
	else c.bk=0;
	return c;
}

void pushdown(int p){
	if(t[p].lazy){
		t[p<<1].color(t[p].lazy);
		t[p<<1|1].color(t[p].lazy);
		t[p].lazy=0;
	}
}

void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(t[p].l==t[p].r){
		t[p].sum=t[p].fr=t[p].ls=1ll* a[l];
		t[p].bk=1;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid); 
	build(p<<1|1,mid+1,r);
	t[p]=t[p<<1]+t[p<<1|1];
}

void add_sum(int p,int l,int r,int x){
	if(t[p].r<l||t[p].l>r) return;
	if(t[p].l>=l&&t[p].r<=r){
		t[p].color(x);
		return;
	}
	pushdown(p);
	
	add_sum(p<<1,l,r,x);
	add_sum(p<<1|1,l,r,x);
	t[p]=t[p<<1]+t[p<<1|1];
}

qwq get_sum(int p,int l,int r){
	if(t[p].r<l||t[p].l>r) return t[0];
	if(t[p].l>=l&&t[p].r<=r)
		return t[p];
	pushdown(p);
	
	qwq ans=get_sum(p<<1,l,r)+get_sum(p<<1|1,l,r);
	return ans;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	
	int opt,l,r;
	int x;
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&opt,&l,&r);
		if(r==n+1) r=n;
		if(opt==1){
			scanf("%d",&x);
			add_sum(1,l,r,x);
		}
		else{
			bool pd=get_sum(1,l,r).bk;
			if(pd) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
}