自动搬运

查看原文

来自洛谷，原作者为

	chenzefan 蒟蒻一枚||六年级||五级钩||GESP七级

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

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

以下是正文

题目传送门

前言

本人在比赛时没有想到这题要用线段树，连暴力都没打，就宣告退出了 （主要是比较懒），现在细细想来，才发现我有多愚蠢。

本题涉及知识

线段树模板，没什么多说的，不懂的点这里。

思路分析

如果已经明白的大佬，可以自行跳过。

看了题目后，发现 $b_i$ 随着 $i$ 的增，始终单调不降，所以我们只需要知道 $b_i$ 的最小值 $\min$ 是多少即可解决问题。

要让 $x$ 的位置的值尽可能小，我们就要用两个线段树分别维护 $a_x$ 和 $a_x-x+1$，于是就有了下面的代码。

线段树做法，时间复杂度 $O(q \times \log n)$。

注意：本题要开 long long。

代码部分（内含注释）

蒟蒻马蜂丑陋，大佬勿喷。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//以下的 p<<1 是 p*2 ，表示左孩子； p<<1|1 是 p*2+1 ，表示右孩子； 
const int N=5e5+5;//题目给的空间
int n,q,a[N];
struct node{
	int l,r,lazy,minn; 
}tree1[4*N],tree2[4*N];//正常开*4的空间~ 
void pushdown1(int p){//处理 tree1 
	if(tree1[p].lazy==0) return ;
	tree1[p<<1].lazy+=tree1[p].lazy;
	tree1[p<<1|1].lazy+=tree1[p].lazy;
	tree1[p<<1].minn+=tree1[p].lazy;
	tree1[p<<1|1].minn+=tree1[p].lazy;
	tree1[p].lazy=0;
} 
void pushdown2(int p){//处理 tree2
	if(tree2[p].lazy==0) return ;
	tree2[p<<1].lazy+=tree2[p].lazy;
	tree2[p<<1|1].lazy+=tree2[p].lazy;
	tree2[p<<1].minn+=tree2[p].lazy;
	tree2[p<<1|1].minn+=tree2[p].lazy;
	tree2[p].lazy=0;
} 
void build1(int p,int l,int r){//处理 tree1 
	tree1[p]={l,r,0,a[l]};//初始化
	if(l==r) return ;
	int mid=l+r>>1;
	//二分建树 
	build1(p<<1,l,mid);build1(p<<1|1,mid+1,r);
	tree1[p].minn=min(tree1[p<<1].minn,tree1[p<<1|1].minn);//更新 p 节点的信息 minn 
} 
void build2(int p,int l,int r){//处理 tree2
	tree2[p]={l,r,0,a[l]-l+1};//初始化 
	if(l==r) return ; 
	int mid=l+r>>1;
	//二分建树
	build2(p<<1,l,mid);build2(p<<1|1,mid+1,r);
	tree2[p].minn=min(tree2[p<<1].minn,tree2[p<<1|1].minn);//更新 p 节点的信息 minn 
} 
void update1(int p,int x,int y,int k){//处理 tree1 
	int l=tree1[p].l;
	int r=tree1[p].r;
	if(x<=l&&r<=y){
		tree1[p].lazy+=k;
		tree1[p].minn+=k;
		return ;
	}pushdown1(p);//处理懒标记 
	int mid=l+r>>1;
	if(x<=mid) update1(p<<1,x,y,k);
	if(y>mid) update1(p<<1|1,x,y,k);
	tree1[p].minn=min(tree1[p<<1].minn,tree1[p<<1|1].minn);//更新 p 节点的信息 minn 
}
void update2(int p,int x,int y,int k){//处理 tree2 
	int l=tree2[p].l;
	int r=tree2[p].r;
	if(x<=l&&r<=y){
		tree2[p].lazy+=k;
		tree2[p].minn+=k;
		return ;
	}pushdown2(p);//处理懒标记 
	int mid=l+r>>1;
	if(x<=mid) update2(p<<1,x,y,k);
	if(y>mid) update2(p<<1|1,x,y,k);
	tree2[p].minn=min(tree2[p<<1].minn,tree2[p<<1|1].minn);//更新 p 节点的信息 minn 
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	//经典建树函数
	build1(1,1,n);build2(1,1,n);
	while(q--){
		int l,r,v;
		scanf("%lld%lld%lld",&l,&r,&v);
		//经典更新函数 
		update1(1,l,r,v);update2(1,l,r,v);
		printf("%lld\n",tree1[1].minn-max(tree2[1].minn,0ll)+1);
	}
	return 0;
}

后附

不要抄袭代码！！不要直接复制！！

先清晰思路，再进行借鉴！！

若有笔误，请指出，感谢。