自动搬运

查看原文

来自洛谷，原作者为

	EDqwq **

搬运于2025-08-24 22:24:14，当前版本为作者最后更新于2020-11-14 23:20:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

定义&本质：

屑其实是什么意思呢？

就是把两个序列头对齐放在一起，只要下面的数全部大于等于上面的数，上面的就比下面的屑。

例如1 3 4 6 7和8 8 8 8

1 3 4 6 7

8 8 8 8

此时，8大于1，8大于3，8大于4，8大于6，所以上面的序列比下面的屑。

那相信先辈是什么意思大家也懂了。

但要什么时候一个序列才是先辈呢？

既然要一个序列的后缀把原序列屑掉，那么这个后缀对齐原序列的头之后，肯定所有的数都大于等于上面的原序列的数，换句话说，也就是需要这个序列是一个不下降序列。

于是这道题就很简单了。

思路：

可以用万能的线段树来做。

我们合并的时候怎么才能判断这个合并出来的区间是不是先辈呢？

我们只需要判断，左边和右边的是不是先辈，然后判断左末和右头满不满足不下降即可。

于是这道题就没有难点了，剩下的都是线段树基本操作。

注意在query里面要用新的merge函数更新即可。

代码：

/*
  Author: EnderDeer
  Online Judge: Luogu
*/

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
	int l;
	int r;
	int lw;
	int rw;
	bool flag;
}e[10000010];

int n,m;
int a[10000010];
int lazy[10000010];

void merge(int i){
	e[i].lw = e[i * 2].lw;
	e[i].rw = e[i * 2 + 1].rw;
	if(e[i * 2].rw <= e[i * 2 + 1].lw && e[i * 2].flag && e[i * 2 + 1].flag)e[i].flag = true;
	else e[i].flag = false;
}

void renewans(node &x,node &y,node &z){
	x.lw = y.lw;
	x.rw = z.rw;
	if(y.flag && z.flag && y.rw <= z.lw)x.flag = true;
	else x.flag = false;
}

void pushup(int i,int w){
	e[i].lw += w;
	e[i].rw += w;
	lazy[i] += w;
}

void pushdown(int i){
	if(e[i].l == e[i].r)return ;
	pushup(i * 2,lazy[i]);
	pushup(i * 2 + 1,lazy[i]);
	lazy[i] = 0;
}

void build(int i,int l,int r){
	e[i].l = l;
	e[i].r = r;
	if(l == r){
		e[i].lw = e[i].rw = a[l];
		e[i].flag = true;
		return ;
	}
	int mid = (l + r) / 2;
	build(i * 2,l,mid);
	build(i * 2 + 1,mid + 1,r);
	merge(i);
}

void update(int i,int l,int r,int w){
	if(e[i].l >= l && e[i].r <= r){
		pushup(i,w);
		return ; 
	}
	pushdown(i);
	int mid = (e[i].l + e[i].r) / 2;
	if(mid >= l)update(i * 2,l,r,w);
	if(mid < r)update(i * 2 + 1,l,r,w);
	merge(i);
}

node query(int i,int l,int r){
	if(e[i].l >= l && e[i].r <= r)return e[i];
	pushdown(i);
	int mid = (e[i].l + e[i].r) / 2;
	node ans;
	node ans1;
	node ans2;
	if(mid >= r)return query(i * 2,l,r);
	else if(mid < l)return query(i * 2 + 1,l,r);
	else {
		ans1 = query(i * 2,l,mid);
		ans2 = query(i * 2 + 1,mid + 1,r);
		renewans(ans,ans1,ans2);
	}
	return ans;
}

signed main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i ++)a[i] = read();
	build(1,1,n);
	while(m --){
		int op;
		int l,r,w;
		op = read();
		if(op == 1){
			l = read(),r = read(),w = read();
			update(1,l,r,w);
		}
		else {
			l = read(),r = read();
			node ans = query(1,l,r);
			if(ans.flag == true)puts("Yes");
			else puts("No");
		}
	}
	return 0;
}