[백준] No.2934 - LRH 식물 (C++, 펜윅 트리)

문제

 

https://www.acmicpc.net/problem/2934

2934번: LRH 식물

 

풀이

 

solved.ac 난이도: Platium 4

 

느리게 갱신되는 세그먼트 트리로 풀 수 있는 문제이지만 원소를 다르게 표현하는 펜윅 트리로도 해결할 수 있다.

 

문제에서 식물의 높이는 항상 이전의 식물들보다 크다.

따라서 이전의 식물들의 구평 선분과 현재 식물의 수직 선분과의 교차점이 꽃이 피는 개수이다.

수평 선분을 구간이라고 생각해보자.

트리에서 해당 구간의 값들을 모두 + 1 씩 증가 시킨다면, 다음 식물과의 교차점은 트리에서의 L과 R위치의 값이 된다.

 

단, 예제의 그림에서 알 수 있듯이 수직 선분끼리의 교차점에서는 꽃이 피지 않으므로  수평 구간은 [L+1, R-1]만이 해당된다.

 

이제 문제에서의 주는 쿼리(질의)를 생각해보자.

Query 1(Range Update): [L+1, R-1]구간의 값들을 + 1로 Update

Query 2(Point query): L과 R위치의 값을 계산

 

기존의 펜윅 트리라면 (백준님이 설명하는 펜윅 트리) 두 가지 기능을 한다.

펜윅 트리 (바이너리 인덱스 트리) - BaekJoon

 

점 업데이트(Point Update): 특정 원소의 값만을 변경

구간 질의(Range Query): 구간의 합을 계산

 

하지만 문제에서 요구하는 쿼리는 반대로 구간 업데이트(Range Update)와 점 질의(Point query)를 요구한다.

따라서 이번 문제에는 기존의 원소 값들의 수열 A []를 B []로 표현하여 펜윅트리의 기능을 변경할 것이다.

 

길이가 N인 수열 A를 다음과 같이 표현해보자.

B[1] =  A[1], B[i] = A[i] - A[i-1]

 

1번 쿼리의 경우: 구간 업데이트(Range Update)

A[i], A[i+1], ... , A[j] 까지에 + k 를 해주어야 한다.

 

이를 B에 대해서 나타내면

B[i] => (A[i] + k) - A[i-1] = B[i] +k

B[i+1] => (A[i+1] + k) - (A[i] + k) = B[i+1]

.

.

.

B[j] => (A[j] + k) - (A[j-1] + k) = B[j]

B[j+1] => A[j+1] - (A[j] + k) = B[j+1] - k

 

즉, B[i]에는 + k, B[j+1]에는 -k만 해주면 구간 업데이트를 구간의 끝점에만 적용해주면 된다.

 

2번 쿼리의 경우 : 점 쿼리(Point query)

A[x]의 값은 B[1] + B[2] +...+ B[x]를 해주면 된다.

A[x] = A[1] + (A[2] - A[1]) + (A[3] - A[2]) + ... + (A[x-1] - A[x-2]) + (A[x] - A[x-1])

(파란 구간의 결국 서로 소거된다.)

 

즉, A를 B로 나타낸 펜윅 트리에서는 A원소의 값을 얻기 위해서 B의 1에서 x까지의 구간 합을 구해주면 된다.

 

그림으로 표현해보자.

일단 배열의 초기 값은 모두 0이다.

 

[3,5]의 구간에 x를 더한다고 하면

B[3] = A[3] - A[2] = x

B[6] = A[6] - A[5] = -x 이므로 각 해당 원소를 update해준다.

 

이 상황에서 A[4]의 값을 구하고 싶다면 

B[4] +  B[3] + B[2] + B[1]의 값을 구하면 된다.

 

B[4](= 0) +  B[3](= 4) + B[2](= 0) + B[1](= 0) = 4

구간의 값 변경에는 원소의 값만 변경하고

오히려 원소 값을 구하기 위해 구간(부분) 합을 이용하는 것을 알 수 있다.

 

 

자, 다시 문제로 돌아오자.

식물의 수평선의 구간 [L+1, R-1]에 + 1을 해주기 위해서는

B[L+1]( = A[L+1] - A[L])에 +1을

B[R-1]( = A[R] - A[R-1])에 -1을 해주면 구간 업데이트가 완료된다!

 

꽃이 피는 개수를 계산하기 위해서는 L과 R위치의 값을 더해주어야 한다.

이는 점 쿼리와 같으므로 A[L] + A[R]을 구하기 위해서는 B로 나타낸  펜윅 트리에서 구간 합(Sum)을 구해야 한다.

( B[L] + B[L - 1] + ... + B[2] + B[1] ) + ( B[R] + B[R - 1] + ... + B[2] + B[1] )

= Sum(L) + Sum(R)

 

추가적으로, 꽃이 핀 곳이라면 더 이상 꽃이 필수 없기 때문에이번에 꽃이 핀 수평선들 교차점은 더 이상 계산에 포함되서는 안 된다.

따라서 해당 위치의 값을 0으로 변경해주면, 더 이상 다음 식물들의 수직선의 교차점 계산에 추가될 일이 없다.

 

단, 이번에는 구간 업데이트 이용하여 점 업데이트를 진행해주어야 한다.

이번의 교차점인 L위치의 기존 값인 Sum(L)을 left_flower라고 하자.

B로 나타낸 펜윅 트리에서 A [L]만을 0으로 만들어 주기 위해서는 A [L]가 포함되는 두 가지 값을 변경해주어야 한다.

B[L] = A[L] - A[L-1]

B[L+1] = A[L+1] - A[L]

 

A[L] 기존의 값 left_flower에서 0으로 변경되었으므로 B[L]은 -left_flower만큼 변경된다.

B[L+1]은 반대로 +left_flower만큼 변경된다.

 

R의 교차점에서도 L과 동일하게 진행해주면 문제를 해결할 수 있다.

 

 

 

코드