线段树板子10分求条 #1AC 玄关

#include <bits/stdc++.h>
using namespace std;
long long a[200005],n,q;
struct node{
	long long l,r,zhi,minn,lz;
}shu[800005]; 
void build(long long l,long long r,long long id){
	shu[id].l = l;
	shu[id].r = r;
	if(l == r){
		shu[id].zhi = a[l];
		shu[id].minn = a[l];
		return;
	}
	long long mid = (l+r)/2;
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
	shu[id].zhi = shu[2*id].zhi + shu[2*id+1].zhi;
	shu[id].minn = min(shu[2*id].minn,shu[2*id+1].minn);
}
void pushdown(long long id){
	if(shu[id].l == shu[id].r) return;
	if(shu[id].lz != 0){
		shu[2*id].lz += shu[id].lz;
		shu[2*id+1].lz += shu[id].lz;
		shu[2*id].zhi += (shu[2*id].r-shu[2*id].l+1)*shu[id].lz;
		shu[2*id+1].zhi += (shu[2*id+1].r-shu[2*id+1].l+1)*shu[id].lz;
		shu[2*id].minn += shu[id].lz;
		shu[2*id+1].minn += shu[id].lz;
		shu[id].lz = 0;
	}
}
void jia(long long l,long long r,long long c,long long id){
	if(shu[id].l >= l && shu[id].r<= r){
		shu[id].zhi += (shu[id].r-shu[id].l+1)*c;
		shu[id].minn += c;
		shu[id].lz += c;
		pushdown(id);
		return;
	}
	if(shu[id].l == shu[id].r ) return;
	if(l <= shu[2*id].r) jia(l,r,c,2*id);
	if(r >= shu[2*id+1].l) jia(l,r,c,2*id+1);
	shu[id].minn = min(shu[2*id].minn,shu[2*id+1].minn);
	shu[id].zhi = shu[2*id].zhi + shu[2*id+1].zhi;
	pushdown(id);
}
long long minum(long long l,long long r,long long id){
	pushdown(id);
	if(shu[id].l >= l && shu[id].r<= r){
		return shu[id].minn;
	}
	long long mum = 1e18;
	if(l <= shu[2*id].r) mum = min(mum,minum(l,r,2*id));
	if(r >= shu[2*id+1].l) mum = min(mum,minum(l,r,2*id+1));
	return mum;
}
long long he(long long l,long long r,long long id){
	pushdown(id);
	if(shu[id].l >= l && shu[id].r<= r){
		return shu[id].zhi;
	}
	long long mum = 0;
	if(l <= shu[2*id].r) mum += he(l,r,2*id);
	if(r >= shu[2*id+1].l) mum += he(l,r,2*id+1);
	return mum;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> q;
	for(long long i = 1;i <= n;i++) cin >> a[i];
	build(1,n,1); 
	while(q--){
		char c;
		cin >> c;
		if(c == 'M'){
			long long md1,md2;
			cin >> md1 >> md2;
			cout << minum(md1,md2,1) << endl;
		}
		else if(c == 'P'){
			long long md1,md2,md3;
			cin >> md1 >> md2 >> md3;
			jia(md1,md2,md3,1);
		}
		else{
			long long md1,md2;
			cin >> md1 >> md2;
			cout << he(md1,md2,1) << endl;
		}
	}
}