KOISTUDY1 [Koistudy] 1396 - 눈 내리는 밤 (L) (C++ cpp) 문제 : koistudy-1396 풀이 현재 n개의 영역의 눈 높이를 arr[i] 로 나타낸다고 해보자. arr[x]는 x 영역의 눈 높이이다. 그리고 F[i] = arr[i] - arr[i-1] 이라고 정의해보자. 그렇다면 arr에 대한 [A, B] 구간을 W만큼 업데이트하는건 F[]로 따졌을 때 다음과 같다. F[A] += W F[B+1] -= W 왜냐하면 F[X] = F[X] - F[X-1] 이므로 F[A]와 F[B+1]을 제외하고는 변화가 없기 때문이다. 즉, 기존 range update가 point update로 변경된다. 다음으로 arr[x]의 값을 알기 위한 쿼리는 F[1] + F[2] + ... + F[X] 로 나타낼 수 있다. 왜냐하면예를들어 X가 5일 경우 F[1] + F[2] + F[.. 2023. 2. 10. 이전 1 다음
