10分 AC#1 线段树求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=210005;
struct node{
	ll l,r,mn,sum,lazy;
}tr[N*4];
ll n,m,a[N];
void pushup(int u) {
	tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
	tr[u].mn=min(tr[u*2].mn,tr[u*2+1].mn);
}
void pushdown(int u) {
	tr[u*2].sum+=tr[u].lazy*(tr[u*2].r-tr[u*2].l+1);
	tr[u*2+1].sum+=tr[u].lazy*(tr[u*2].r-tr[u*2].l+1);
	tr[u*2].mn+=tr[u].lazy;
	tr[u*2+1].mn+=tr[u].lazy;
	tr[u*2].lazy+=tr[u].lazy;
	tr[u*2+1].lazy+=tr[u].lazy;
	tr[u].lazy=0;
}
void build(int u,int l,int r) {
	tr[u].l=l;
	tr[u].r=r;
	if (l==r) {
		tr[u].sum=a[l];
		tr[u].mn=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}
void update(int u,int l,int r,int x) {
	if (tr[u].l==l && tr[u].r==r) {
		tr[u].sum+=x*(tr[u].r-tr[u].l+1);
		tr[u].lazy+=x;
		tr[u].mn+=x;
		return ;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if (r<=mid) update(u*2,l,r,x);
	else if (l>mid) update(u*2+1,l,r,x);
	else {
		update(u*2,l,mid,x);
		update(u*2+1,mid+1,r,x);
	}
	pushup(u);
}
int query1(int u,int l,int r) {
	if (tr[u].l==l && tr[u].r==r) {
		return tr[u].mn;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if (r<=mid) return query1(u*2,l,r);
	else if (l>mid) return query1(u*2+1,l,r);
	else return min(query1(u*2,l,mid),query1(u*2+1,mid+1,r));
}
int query2(int u,int l,int r) {
	if (tr[u].l==l && tr[u].r==r) {
		return tr[u].sum;
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if (r<=mid) return query2(u*2,l,r);
	else if (l>mid) return query2(u*2+1,l,r);
	else return query2(u*2,l,mid)+query2(u*2+1,mid+1,r);
}
int main() {
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for (int i=1;i<=m;i++) {
		char op;
		int l,r,x;
		cin>>op;
		if (op=='P') {
			cin>>l>>r>>x;
			update(1,l,r,x);
		}else if (op=='M') {
			cin>>l>>r;
			cout<<query1(1,l,r)<<endl;
		}else if (op=='S') {
			cin>>l>>r;
			cout<<query2(1,l,r)<<endl;
		}
	}
	return 0;
}