레이팅 미적용농부 존은 농장을 재정비하는 일을 도울 인부들을 고용하려 하지만, 지금까지 온 인부들은 모두 FJ가 따르라고 한 복잡한 지시 목록을 보고는 그만두어 버렸다. 혼자서 프로젝트를 마무리하게 된 FJ는 정말로 자신이 프로젝트를 필요 이상으로 복잡하게 만들었을지도 모른다는 것을 깨달았다. FJ가 지시를 따라 농장 업그레이드를 완료할 수 있도록 도와주자.
FJ의 농장은 한 줄로 늘어선 \(N\)개의 밭으로 이루어져 있으며, \(1 \ldots N\)의 번호가 붙어 있다. 각 밭에는 건초 더미가 몇 개든 있을 수 있다. 농부 존의 지시는 세 가지 종류의 항목으로 이루어져 있다:
1) 연속된 밭 구간이 주어지면, 그 구간의 각 밭에 새 건초 더미를 하나씩 추가한다.
2) 연속된 밭 구간이 주어지면, 그 구간 안의 밭 하나에 있는 건초 더미 수의 최솟값을 구한다.
3) 연속된 밭 구간이 주어지면, 그 구간 안에 있는 건초 더미의 총 개수를 센다.
Problem credits: Nick Wu
Problem credits: Nick Wu
첫째 줄에 두 양의 정수 \(N\)(\(1 \leq N \leq 200,000\))과 \(Q\)(\(1 \leq Q \leq 100,000\))가 주어진다.
다음 줄에 각 밭에 처음에 있는 건초 더미의 수를 나타내는, 각각 최대 100,000인 음이 아닌 정수 \(N\)개가 주어진다.
다음 \(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' 항목마다 출력에 한 줄이 나와야 한다.
haybales.in · 출력을 쓸 파일 haybales.out4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 32
6
3
8riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Platinum