NC24024. [USACO 2015 Dec P]Counting Haybales
描述
FJ's farm consists of NN fields in a row, conveniently numbered 1…N1…N. In each field there can be any number of haybales. Farmer John's instructions contain three types of entries:
1) Given a contiguous interval of fields, add a new haybale to each field.
2) Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval.
3) Given a contiguous interval of fields, count the total number of haybales inside that interval.
输入描述
The first line contains two positive integers, NN (1≤N≤200,0001≤N≤200,000) and QQ (1≤Q≤100,0001≤Q≤100,000).
The next line contains NN nonnegative integers, each at most 100,000, indicating how many haybales are initially in each field.
Each of the next QQ lines contains a single uppercase letter, either M, P or S, followed by either two positive integers AA and BB (1≤A≤B≤N1≤A≤B≤N), or three positive integers AA, BB, and CC (1≤A≤B≤N1≤A≤B≤N; 1≤C≤100,0001≤C≤100,000). There will be three positive integers if and only if the uppercase letter is P.
If the letter is M, print the minimum number of haybales in the interval of fields from A…BA…B.
If the letter is P, put CC new haybales in each field in the interval of fields from A…BA…B.
If the letter is S, print the total number of haybales found within interval of fields from A…BA…B.
输出描述
A line in the output should appear in response to every 'M' or 'S' entry in FJ's instructions.
示例1
输入:
4 5 3 1 2 4 M 3 4 S 1 3 P 2 3 1 M 3 4 S 1 3
输出:
2 6 3 8
C++(clang++11) 解法, 执行用时: 233ms, 内存消耗: 17580K, 提交时间: 2021-02-10 23:35:53
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 200010
using namespace std;
int n,m;
struct nond
{
int l,r;
long long min,sum,flag;
}tree[MAXN*4];
void up(int now)
{
tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
tree[now].min=min(tree[now*2].min,tree[now*2+1].min);
}
void build(int now,int l,int r)
{
tree[now].l=l;
tree[now].r=r;
if(tree[now].l==tree[now].r)
{
scanf("%lld",&tree[now].sum);
tree[now].min=tree[now].sum;
return;
}
int mid=(tree[now].l+tree[now].r)/2;
build(now*2,l,mid);
build(now*2+1,mid+1,r);
up(now);
}
void down(int now)
{
tree[now*2].flag+=tree[now].flag;
tree[now*2+1].flag+=tree[now].flag;
tree[now*2].min+=tree[now].flag;
tree[now*2+1].min+=tree[now].flag;
tree[now*2].sum+=(tree[now*2].r-tree[now*2].l+1)*tree[now].flag;
tree[now*2+1].sum+=(tree[now*2+1].r-tree[now*2+1].l+1)*tree[now].flag;
tree[now].flag=0;
}
void change(int now,int l,int r,long long opt)
{
if(tree[now].l==l&&tree[now].r==r)
{
tree[now].min+=opt;
tree[now].flag+=opt;
tree[now].sum+=(tree[now].r-tree[now].l+1)*opt;
return;
}
if(tree[now].flag)
down(now);
int mid=(tree[now].l+tree[now].r)/2;
if(r<=mid)
change(now*2,l,r,opt);
else if(l>mid)
change(now*2+1,l,r,opt);
else
{
change(now*2,l,mid,opt);
change(now*2+1,mid+1,r,opt);
}
up(now);
}
long long query(int now,int l,int r,int opt)
{
if(tree[now].l==l&&tree[now].r==r)
{
if(opt==1)
return tree[now].sum;
else
return tree[now].min;
}
if(tree[now].flag)
down(now);
int mid=(tree[now].l+tree[now].r)/2;
if(r<=mid)
return query(now*2,l,r,opt);
else if(l>mid)
return query(now*2+1,l,r,opt);
else
{
if(opt==1)
return query(now*2,l,mid,opt)+query(now*2+1,mid+1,r,opt);
else
return min(query(now*2,l,mid,opt),query(now*2+1,mid+1,r,opt));
}
}
int main()
{
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i++)
{
char s[10];
int x,y,z;
scanf("%s%d%d",s,&x,&y);
if(s[0]=='S')
cout<<query(1,x,y,1)<<endl;
if(s[0]=='M')
cout<<query(1,x,y,0)<<endl;
if(s[0]=='P')
{
scanf("%lld",&z);
change(1,x,y,z);
}
}
}