갱신의 제왕
다이아몬드 II의견: 0
길이 \(N\)의 정수 수열 \(a_1, a_2, \dots, a_N\)이 주어진다. 다음 네 종류의 연산을 총 \(Q\)번 처리해야 한다.
-
1 l r x: 모든 \(i \in [l, r]\)에 대해 \(a_i \leftarrow \min(a_i, x)\) -
2 l r x: 모든 \(i \in [l, r]\)에 대해 \(a_i \leftarrow \max(a_i, x)\) -
3 l r x: 모든 \(i \in [l, r]\)에 대해 \(a_i \leftarrow a_i + x\) -
4 l r: \(\sum_{i=l}^{r} a_i\) 를 출력
구간 \(\min\)/\(\max\) 갱신과 구간 덧셈, 구간 합 질의를 모두 동시에 빠르게 처리해야 한다.
\(1 \le N, Q \le 200{,}000\)
\(-10^9 \le a_i \le 10^9\)
\(1\), \(2\) 연산의 \(x\)는 \(-10^9 \le x \le 10^9\)
\(3\) 연산의 \(x\)는 \(-10^4 \le x \le 10^4\)
\(1 \le l \le r \le N\)
첫 줄에 \(N\)과 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 연산이 한 줄에 하나씩 주어진다.
각 4 연산에 대해 해당 구간의 합을 한 줄에 하나씩 출력한다.
5 5
1 4 2 5 3
1 2 4 3
3 1 5 2
4 1 5
2 1 3 5
4 1 5
22
25초기 [1,4,2,5,3]. 연산1(min 3 on [2,4]) -> [1,3,2,3,3]. 연산3(+2 전체) -> [3,5,4,5,5], 합=22. 연산4 출력 22. 연산2(max 5 on [1,3]) -> [5,5,5,5,5], 전체 합=25. 연산4 출력 25.
3 3
10 -3 7
4 1 3
2 1 3 0
4 1 3
14
17초기 [10,-3,7], 합=14. max 0 적용 -> [10,0,7], 합=17.
riseoj 작성
출처 Original
평가 및 의견
갱신의 제왕
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
갱신의 제왕