USACO 2015 December Contest, Platinum
Problem 3. Counting Haybales
Contest has ended.
Log in to allow submissions in analysis mode
FJ's farm consists of $N$ fields in a row, conveniently numbered $1 \ldots 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.
INPUT FORMAT (file haybales.in):
The first line contains two positive integers, $N$ ($1 \leq N \leq 200,000$) and $Q$ ($1 \leq Q \leq 100,000$).The next line contains $N$ nonnegative integers, each at most 100,000, indicating how many haybales are initially in each field.
Each of the next $Q$ lines contains a single uppercase letter, either M, P or S, followed by either two positive integers $A$ and $B$ ($1 \leq A \leq B \leq N$), or three positive integers $A$, $B$, and $C$ ($1 \leq A \leq B \leq N$; $1 \leq C \leq 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 B$.
If the letter is P, put $C$ new haybales in each field in the interval of fields from $A \ldots B$.
If the letter is S, print the total number of haybales found within interval of fields from $A \ldots B$.
OUTPUT FORMAT (file haybales.out):
A line in the output should appear in response to every 'M' or 'S' entry in FJ's instructions.SAMPLE INPUT:
4 5 3 1 2 4 M 3 4 S 1 3 P 2 3 1 M 3 4 S 1 3
SAMPLE OUTPUT:
2 6 3 8
Problem credits: Nick Wu