oVeron

1.구간을 갱신하는 문제이므로 무조건 lazy propagation을 써야 한다. 먼저 세그먼트 트리, lazy에 어떤 값을 넣어줄지 결정하자. 더하기 연산은 구간의 최솟값, 빼기 연산은 구간의 최댓값을 갱신하는 것과 다름없다. \(h\) 값에 따라 구간의 최댓값, 최솟값이 갱신되므로, 세그먼트 트리, lazy에 pair 형태로 {구간의 최솟값, 구간의 최댓값}을 저장해 주자. 2.세그먼트 트리와 lazy에 값을 저장했다 가정하자. 그렇다면 쿼리가 들어올 때 높이를 어떻게 lazy해야 하는가? 위에서 더하기 연산은 구간의 최솟값, 빼기 연산은 구간의 최댓값을 갱신하는 것이라고 했다. 그렇다면 더하기 연산의 최댓값이 빼기 연산의 최솟값보다 크면 어떻게 될까? 예를 들어 높이 5로 빼는 연산을 진행한 후 높..

알고리즘/baekjoon 2024. 7. 20. 14:10