Counting Haybales

题目描述

农夫 John 正在尝试雇佣承包商来帮助重新整理他的农场，但到目前为止，所有人看到 FJ 想让他们遵循的复杂指令序列后都辞职了。由于只能自己完成该项目，他意识到自己确实把项目搞得可能比必要的更复杂。请帮助他遵循这些指令来完成农场升级。

FJ 的农场由一排 $N$ 块田地组成，方便起见编号为 $1 \ldots N$。每块田地中可以有任意数量的干草捆。FJ 的指令包含三种类型的操作：

1. 给定一个连续的田地区间，给区间内每块田地都增加一个新的干草捆。
2. 给定一个连续的田地区间，确定该区间内某块田地的干草捆数量的最小值。
3. 给定一个连续的田地区间，统计该区间内干草捆的总数。

输入格式

第一行包含两个正整数，$N$ ($1 \leq N \leq 200,000$) 和 $Q$ ($1 \leq Q \leq 100,000$)。 下一行包含 $N$ 个非负整数，每个最多为 100,000，表示每块田地初始拥有的干草捆数量。 接下来的 $Q$ 行中，每行包含一个大写字母（M、P 或 S），后面跟着两个正整数 $A$ 和 $B$（$1 \leq A \leq B \leq N$），或三个正整数 $A$、$B$ 和 $C$（$1 \leq A \leq B \leq N$；$1 \leq C \leq 100,000$）。当且仅当大写字母为 P 时，该行会有三个正整数。 如果字母是 M，输出田地区间 $A \ldots B$ 内干草捆数量的最小值。 如果字母是 P，在田地区间 $A \ldots B$ 内每块田地都增加 $C$ 个新的干草捆。 如果字母是 S，输出田地区间 $A \ldots B$ 内干草捆的总数量。

输出格式

对于 FJ 指令中每条 'M' 或 'S' 操作，输出中都应有一行对应的结果。

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

提示

题目来源：Nick Wu

标签: USACO|2015|Platinum

来源

USACO|2015|Platinum