구간 최솟값 갱신과 합
다이아몬드 V의견: 0
길이 \(N\)인 정수 수열 \(a_1, \dots, a_N\)이 주어진다. 다음 두 종류의 질의 \(Q\)개를 순서대로 처리해야 한다.
-
1 l r x: 구간 \([l, r]\)의 모든 \(i\)에 대해 \(a_i \leftarrow \min(a_i, x)\)로 갱신한다. -
2 l r: 구간 \([l, r]\)의 원소 합 \(\sum_{i=l}^{r} a_i\)를 출력한다.
구간 \(\min\) 갱신은 단순 lazy로는 처리하기 어렵다.
\(1 \le N, Q \le 200{,}000\)
\(0 \le a_i \le 10^9\)
갱신 질의의 \(x\)는 \(0 \le x \le 10^9\)
첫 줄에 \(N\)과 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
이후 \(Q\)개의 줄에 질의가 위 형식으로 주어진다. (\(1 \le l \le r \le N\))
각 2번 질의에 대해 구간 합을 한 줄에 하나씩 출력한다.
5 4
1 5 3 2 4
1 2 4 3
2 1 5
1 1 5 2
2 1 5
13
9초기 \([1,5,3,2,4]\). 1 2 4 3으로 인덱스 2..4에 min(.,3) 적용 → \([1,3,3,2,4]\), 전체 합 \(13\). 이어 1 1 5 2로 전체 min(.,2) → \([1,2,2,2,2]\), 합 \(9\).
3 5
10 10 10
2 1 3
1 1 3 10
2 1 3
1 2 2 5
2 1 3
30
30
25초기 합 \(30\). 1 1 3 10은 변화 없어 합 \(30\). 1 2 2 5로 둘째 원소 \(5\) → \([10,5,10]\), 합 \(25\).
riseoj 작성
출처 Original
평가 및 의견
구간 최솟값 갱신과 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 최솟값 갱신과 합