페인트칠 공사
플래티넘 IV의견: 0
길이 \(N\)인 복도의 벽을 리모델링하기로 했다. 벽은 \(1\)번부터 \(N\)번까지 번호 붙인 \(N\)개의 칸으로 이루어져 있고, 처음에 모든 칸의 페인트 두께는 \(0\)이다.
페인트칠 공사는 두 가지 작업으로 이루어진다.
- 1 l r v : \(l\)번부터 \(r\)번 칸의 페인트를 두께 \(v\)로 덮어쓴다. 이전에 칠해진 페인트는 모두 제거된다.
- 2 l r : \(l\)번부터 \(r\)번 칸의 페인트 두께 합을 출력한다.
각 쿼리를 순서대로 처리하여라.
- \(1 \le N \le 200\,000\)
- \(1 \le Q \le 200\,000\)
- 타입 \(1\) 쿼리: \(1 \le l \le r \le N\), \(0 \le v \le 10^9\)
- 타입 \(2\) 쿼리: \(1 \le l \le r \le N\)
- 타입 \(2\) 쿼리는 \(1\)개 이상 존재한다.
- 출력되는 값은 \(2 \times 10^{14}\) 이하임이 보장된다.
첫째 줄에 칸의 수 \(N\)과 쿼리 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 쿼리가 주어진다. 쿼리의 첫 번째 숫자가 \(1\)이면 1 l r v 형식이고, \(2\)이면 2 l r 형식이다.
타입 \(2\) 쿼리마다 답을 한 줄씩 출력한다.
4 4
1 1 4 7
1 2 3 3
2 1 4
2 1 1
20
7
먼저 \([1,4]\) 구간을 \(7\)로 칠하면 \([7,7,7,7]\)이다. 이후 \([2,3]\) 구간을 \(3\)으로 덮으면 \([7,3,3,7]\)이 된다. \([1,4]\) 합은 \(7+3+3+7=20\), \([1,1]\) 합은 \(7\)이다.
5 6
1 1 5 5
2 1 5
1 3 5 0
2 1 5
1 1 2 10
2 1 5
25
10
20
\([1,5]\)을 \(5\)로 칠하면 \([5,5,5,5,5]\), 합 \(25\). \([3,5]\)을 \(0\)으로 칠하면 \([5,5,0,0,0]\), 합 \(10\). \([1,2]\)을 \(10\)으로 칠하면 \([10,10,0,0,0]\), 합 \(20\).
riseoj 작성
출처 Original
평가 및 의견
페인트칠 공사
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
페인트칠 공사