问题描述

输入一个长为n的数列a[1],a[2],a[3]…a[n]，以及m个操作，请你输出这些操作的结果，每次操作是以下两种之一：

• (1)数列中某连续一段全部+1
• (2)求数列中某连续一段的最小值，并输出这个值

输入格式

• 第一行：n m
• 接下去n行：a[1],a[2],a[3]…a[n]
• 接下去m行：每行“1 l r”表示修改或者“2 l r"表示查询。

输出格式

• 每个查询用一行输出。

样例输入

1 1
1
2 1 1

样例输出

1

数据规模和约定

• n,m<=$10^{5}$
• a[i]<=$10^{6}$

本人线段树解法求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long w[N<<2],a[N],n,m,lzy[N<<2]; 
void pushup(int u){
 w[u]=min(w[2*u],w[2*u+1]);
 }

void build(int u,int L,int R){
 if(L==R){
	w[u]=a[L];
 	return ;
 }
 int mid=(L+R)/2;
 build(2*u,L,mid);
 build(2*u+1,mid+1,R);
 pushup(u);
}
void update1(int u,int L,int R,int p,int x){
 if(L==R){
	w[u]+=x;
	return ;
 }
 int mid=(L+R)/2;
 if(p<=mid) update1(2*u,L,mid,p,x);
 else update1(2*u+1,mid+1,R,p,x);
	pushup(u);
}
bool inRange(int L,int R,int l,int r){
 return l<=L && R<=r;
 }
bool outofRange(int L,int R,int l,int r){
 return r<L || R<l;
 }
 void maketag(int u,int L,int R,long long x){

	lzy[u]+=x;
 	w[u]+=(R-L+1)*x;
 }

void pushdown(int u,int L,int R){
	 int mid=(L+R)/2;
	 maketag(2*u,L,mid,lzy[u]);
	 maketag(2*u+1,mid+1,R,lzy[u]);
	 lzy[u]=0;
 }

void update(int u,int L,int R,int l,int r,long long x){
	if(inRange(L,R,l,r)){
		maketag(u,L,R,x);
	}else if(!outofRange(L,R,l,r)){
	int mid=(L+R)/2;
 	pushdown(u,L,R);
	update(2*u,L,mid,l,r,x);
	update(2*u+1,mid+1,R,l,r,x);
 	pushup(u);
 	
	 }
}
long long query(int u,int L,int R,int l,int r){
	if(inRange(L,R,l,r)){
 		return w[u];
	 }else if(outofRange(L,R,l,r)){
 		return 0;
 	}else{
 		int mid=(L+R)/2;
 		pushdown(u,L,R);
 		return min(query(2*u,L,mid,l,r),query(2*u+1,mid+1,R,l,r));
	 }
}
int main(){	
	int op,x,y,k=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		cin>>op>>x>>y;
		if(op==1){
			update(1,1,n,x,y,k);
		}else{
			cout<<query(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}