구간 더하기와 합·최솟값
플래티넘 IV의견: 0
수열 위에서 두 가지 갱신과 두 가지 질의를 빠르게 처리해야 한다. 길이가 \(N\)인 정수 수열 \(A_1, A_2, \dots, A_N\)이 주어진다. 다음 세 종류의 연산이 총 \(Q\)개 주어진다.
1 l r v: 구간 \([l, r]\)의 모든 원소에 \(v\)를 더한다.2 l r: 구간 \([l, r]\)의 합을 출력한다.3 l r: 구간 \([l, r]\)의 최솟값을 출력한다.
구간 갱신과 구간 질의를 모두 효율적으로 처리하려면 느리게 갱신되는 세그먼트 트리가 필요하다.
\(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\)가 공백으로 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 주어진다.
이후 \(Q\)개의 줄에 연산이 위 형식대로 주어진다.
타입 2 또는 3 질의마다 답을 한 줄에 하나씩 출력한다.
5 5
1 2 3 4 5
2 1 5
1 2 4 10
2 1 5
3 1 3
1 1 5 1
15
45
1초기 합 \(1+2+3+4+5=15\). 구간 \([2,4]\)에 10을 더한 뒤 전체 합은 \(15+30=45\). 그 상태에서 \([1,3]\)의 최솟값은 \(A=[1,12,13,4,5]\)이므로 1.
3 4
-1 -1 -1
3 1 3
1 1 2 5
2 1 3
3 1 3
-1
7
-1처음 \([1,3]\) 최솟값은 \(-1\). \([1,2]\)에 5를 더하면 \(A=[4,4,-1]\), 합 \(7\), 최솟값 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
구간 더하기와 합·최솟값
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 더하기와 합·최솟값