[USACO15DEC] Counting Haybale P 题解（线段树）

题目链接

题目简单来说就是，给你n个数，并可以对其中任意一个区间进行如下 *** 作：

1. 给定一个连续区间，在该区间内的每个数都加上某个数
2. 给定一个连续区间，找出该区间的最小数
3. 给定一个连续区间，求出该区间的和

其实，把题目理解透彻之后，基本上就知道要求什么了。

没错，这是一道蓝题（提高+/省选-），但其实没有那么的难，只是代码实现上可能会有问题。

我个人感觉应该是绿题（晋级+/提高-）的难度。

直接把线段树糊上去就行了，注意取最小值时懒标记的更新方法，还有就是开long long。

如果线段树有问题的话，可以看看我之前写过的线段树学习笔记

#include
#include
#include
#include
#include
using namespace std;

const int maxn=1010001;
long long n,m;

struct tree{
	long long l;
	long long r;
	long long k;
	long long val;
	long long minn;
}t[4*maxn];

void build(long long k,long long l,long long r){
	t[k].l=l,t[k].r=r;
	if(t[k].l==t[k].r){
		scanf("%lld",&t[k].val);
		t[k].minn=t[k].val;
		return;
	}
	long long mid=(l+r)>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	t[k].val=t[k*2].val+t[k*2+1].val;
	t[k].minn=min(t[k*2].minn,t[k*2+1].minn);
}

void down(long long k){
	t[k*2].k+=t[k].k;
	t[k*2+1].k+=t[k].k;
	t[k*2].minn+=t[k].k;//注意这里！！！
	t[k*2+1].minn+=t[k].k;//注意这里！！！
	t[k*2].val+=(t[k*2].r-t[k*2].l+1)*t[k].k;
	t[k*2+1].val+=(t[k*2+1].r-t[k*2+1].l+1)*t[k].k;
	t[k].k=0;
}

void change_line(long long k,long long a,long long b,long long y){
	if(t[k].l>=a&&t[k].r<=b){
		t[k].k+=y;
		t[k].minn+=y;
		t[k].val+=(t[k].r-t[k].l+1)*(long long)y;
		return ;
	}
	if(t[k].k) down(k);
	long long mid=(t[k].l+t[k].r)>>1;
	if(a<=mid) change_line(k*2,a,b,y);
	if(b>mid) change_line(k*2+1,a,b,y);
	t[k].val=t[k*2].val+t[k*2+1].val;
	t[k].minn=min(t[k*2].minn,t[k*2+1].minn);
}

long long query_sum(long long k,long long a,long long b){
	long long ans=0;
	if(t[k].l>=a&&t[k].r<=b){
		return t[k].val;
	}
	if(t[k].k) down(k);
	long long mid=(t[k].l+t[k].r)>>1;
	if(a<=mid) ans+=query_sum(k*2,a,b);
	if(b>mid) ans+=query_sum(k*2+1,a,b);
	return ans;
}

long long query_min(long long k,long long a,long long b){
	if(t[k].l>=a&&t[k].r<=b){
		return t[k].minn;
	}
	if(t[k].k) down(k);
	long long mid=(t[k].l+t[k].r)>>1;
	long long ans=0x3f3f3f3f;
	if(a<=mid) ans=min(ans,query_min(k*2,a,b));
	if(b>mid) ans=min(ans,query_min(k*2+1,a,b));
	return ans;
}

int main(){
	cin>>n>>m;
	build(1,1,n);
	while(m--){
		char c;
		int x,y,z;
		cin>>c;
		cin>>x>>y;
		if(c=='P'){
			cin>>z;
			change_line(1,x,y,z);
		}
		if(c=='S') cout<