구간 클램프 합
다이아몬드 IV의견: 0
길이 \(N\)의 정수 수열 \(A_1, A_2, \dots, A_N\)이 주어진다. 이 수열에 대해 다음 네 종류의 연산을 \(M\)번 수행한다.
-
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\) (구간 더하기, \(x\)는 음수일 수 있다) -
4 l r: \(\sum_{i=l}^{r} A_i\)를 출력한다 (구간 합 질의)
네 종류의 연산이 섞여 들어오므로 일반적인 지연 전파 세그먼트 트리로는 처리하기 어렵다.
\(1 \le N, M \le 50{,}000\)
\(1 \le l \le r \le N\)
\(|A_i| \le 10^9\)
\(1\), \(2\)번 연산의 \(x\): \(|x| \le 10^9\)
\(3\)번 연산의 \(x\): \(|x| \le 10^5\)
첫 줄에 두 정수 \(N\), \(M\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 공백으로 구분되어 주어진다.
이어서 \(M\)개의 줄에 위에서 설명한 형식의 연산이 한 줄에 하나씩 주어진다.
각 4번 연산에 대해 해당 구간의 합을 한 줄에 하나씩 출력한다.
5 6
3 1 4 1 5
1 1 5 3
4 1 5
2 2 4 2
4 1 5
3 1 3 10
4 1 5
11
13
43초기 [3,1,4,1,5]. 1번: 모두 3 이하로 -> [3,1,3,1,3], 합 11. 2번: 인덱스 2..4를 2 이상으로 -> [3,2,3,2,3], 합 13. 3번: 인덱스 1..3에 10 더하기 -> [13,12,13,2,3], 합 43.
3 6
-2 0 5
4 1 3
2 1 3 0
4 1 3
1 1 3 1
3 2 2 -10
4 1 3
3
5
-9초기 [-2,0,5], 합 3. 모두 0 이상으로 -> [0,0,5], 합 5. 모두 1 이하로 -> [0,0,1], 합 1. 인덱스 2에 -10 -> [0,-10,1], 합 -9.
riseoj 작성
출처 Original
평가 및 의견
구간 클램프 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 클램프 합