구름 농장
플래티넘 V의견: 0
마법 왕국의 농부 아르뇨는 \(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\), \(1 \le v \le 10^9\)
- 타입 \(2\) 쿼리: \(1 \le l \le r \le N\)
- 타입 \(2\) 쿼리는 \(1\)개 이상 존재한다.
- 출력되는 값은 \(10^{18}\) 이하임이 보장된다.
첫째 줄에 밭의 수 \(N\)과 쿼리 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 쿼리가 주어진다. 각 쿼리의 첫 번째 숫자가 \(1\)이면 1 l r v 형식이고, \(2\)이면 2 l r 형식이다.
타입 \(2\) 쿼리마다 답을 한 줄씩 출력한다.
4 4
1 1 3 5
1 2 4 3
2 1 4
2 2 3
24
16
구간 \([1,3]\)에 \(5\)를 더하면 배열은 \([5, 5, 5, 0]\)이고, 구간 \([2,4]\)에 \(3\)을 더하면 \([5, 8, 8, 3]\)이 된다. \([1,4]\) 구간 합은 \(5+8+8+3=24\), \([2,3]\) 구간 합은 \(8+8=16\)이다.
5 4
1 1 5 2
2 1 5
1 3 3 10
2 3 3
10
12
구간 \([1,5]\)에 \(2\)를 더하면 \([2,2,2,2,2]\), 합은 \(10\)이다. 이후 \(3\)번 칸에 \(10\)을 더하면 \([2,2,12,2,2]\), \([3,3]\) 합은 \(12\)이다.
riseoj 작성
출처 Original
평가 및 의견
구름 농장
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구름 농장