R00381
구간 대입과 구간 합
플래티넘 IV레이팅
의견: 0
설명
길이가 \(N\)인 정수 수열 \(A_1, \dots, A_N\) 위에서 다음 연산을 처리한다.
1 l r v: 구간 \([l, r]\)의 모든 원소를 값 \(v\)로 덮어쓴다(대입).2 l r: 구간 \([l, r]\)의 합을 출력한다.
구간 대입 연산은 lazy 전파에서 덧셈과 달리 '덮어쓰기'로 처리해야 한다.
제약
\(1 \le N, Q \le 100{,}000\)
\(-10^6 \le A_i \le 10^6\), 갱신 값 \(|v| \le 10^6\)
\(1 \le l \le r \le N\)
입력 형식
첫 줄에 \(N\), \(Q\).
둘째 줄에 \(A_1, \dots, A_N\).
이후 \(Q\)줄에 1 l r v(대입) 또는 2 l r(합 질의).
출력 형식
타입 2 질의마다 답을 한 줄에 출력한다.
예제 1
입력
5 4
1 2 3 4 5
2 1 5
1 2 4 7
2 1 5
2 2 4
출력
15
27
21설명
초기 합 15. \([2,4]\)를 모두 7로 대입하면 \(A=[1,7,7,7,5]\), 전체 합 27, \([2,4]\) 합 21.
예제 2
입력
4 3
10 20 30 40
1 1 4 0
2 1 4
1 2 3 5
출력
0설명
\([1,4]\)를 0으로 대입하면 모두 0, 전체 합 0. 이후 \([2,3]\)을 5로 대입(질의 없음).
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
구간 대입과 구간 합
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 대입과 구간 합
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기