洛谷P3130 Counting Haybale P

CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/16
（请不要删掉此地址）

传送门

题目描述

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has made the project perhaps more complicated than necessary. Please help him follow his instructions to complete the farm upgrade.

FJ’s farm consists of NN fields in a row, conveniently numbered 1 \ldots N1…N. In each field there can be any number of haybales. Farmer John’s instructions contain three types of entries:

Given a contiguous interval of fields, add a new haybale to each field.

Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval.

Given a contiguous interval of fields, count the total number of haybales inside that interval.

FJ像雇佣几个人在他的农场里帮忙，他需要进行很多种操作，请你帮他搞定。

FJ的农场有N块田地排长一行，编号是从1到N的。每一块田地都有很多草包。FJ要进行下面几种操作：

1)给定一段连续的田地，给每一个田地都增加一些新的草包。

2)给定一段连续的田地，找出草包最少的田地有多少草包。

3)给定一段连续的田地，统计一共有多少草包。

输入格式

The first line contains two positive integers, NN (1 \leq N \leq 200,0001≤N≤200,000) and

QQ (1 \leq Q \leq 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 \leq A \leq B \leq N1≤A≤B≤N),

or three positive integers AA, BB, and CC (1 \leq A \leq B \leq N1≤A≤B≤N;

1 \leq C \leq 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 \ldots BA…B.

If the letter is P, put CC new haybales in each field in the interval of fields

from A \ldots BA…B.

If the letter is S, print the total number of haybales found within interval of

fields from A \ldots 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
输出 #1复制
2
6
3
8

上代码：

#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N=400000;
int n,m,a[N];
char c;
struct tree
{
    int l;
    int r;
    int min;
    int sum;
    int add;
}t[N<<2];//四倍
void pushup(int p)
{
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
void pushdown(int p)
{
	if(!t[p].add)return;
    t[p<<1|1].add+=t[p].add; 
	t[p<<1].add+=t[p].add;	
	t[p<<1].min+=t[p].add;
	t[p<<1|1].min+=t[p].add;
	t[p<<1|1].sum+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].add;
	t[p<<1].sum+=(t[p<<1].r-t[p<<1].l+1)*t[p].add;
	t[p].add=0;//不要忘了清零
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].min=t[p].sum=a[l];return;}
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    pushup(p);//别忘了传递
}
void change(int p,int l,int r,int z)
{
    if(l<=t[p].l&&r>=t[p].r){t[p].add+=z,t[p].min+=z,t[p].sum+=(t[p].r-t[p].l+1)*z;return;}
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)change(p<<1,l,r,z);
    if(r>mid)change(p<<1|1,l,r,z);
    pushup(p);//传递
}
int querysum(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
    pushdown(p);//懒标记要向下传递信息；
    int mid=t[p].l+t[p].r>>1;
    int ans=0;
    if(l<=mid)ans+=querysum(p<<1,l,r);
    if(r>mid)ans+=querysum(p<<1|1,l,r);
    return ans;
}
int querymin(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)return t[p].min;
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    int ans=0x7f7f7f7f;
    if(l<=mid)ans=querymin(p<<1,l,r);
    if(r>mid)ans=min(ans,querymin(p<<1|1,l,r));
    return ans;
}//这个和sum没什么区别吧，嘻嘻
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>c;
        if(c=='P')
        {
            int l,r,z;
            scanf("%lld%lld%lld",&l,&r,&z);
            change(1,l,r,z);
        }
        if(c=='M')
        {
            int l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",querymin(1,l,r));
        }
        if(c=='S')
        {
            int l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",querysum(1,l,r));
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104