boj 2934 : CVJETICI

boj 2934 : CVJETICI(LRH 식물)

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

펜윅트리를 이용하여 해결할 수있다.

울타리 기둥의 좌표가 주어졌을 때 그 울타리를 가로지르는 팬스의 갯수를 구하는 데 펜윅트리를 이용한다.

먼저 펜윅트리는 구간의 합을 빠르게 구하는 데 쓰인다. 이를 응용하면 좌표가 주어졌을 때 '그 좌표를 포함하는 구간들' 의 갯수를 빠르게 구할 수 있다.

울타리의 left, right가 주어질 때 add(left + 1,1), add(right,-1)이렇게 하면 해당구간을 가로지르는 펜스의 갯수를 누적할 수 있다.

이렇게 하면 sum연산으로 누적되어있는 울타리의 수를 알아낼 수 있다.

그렇다면 남은건 이미 피어있는 꽃에 대한 처리는 어떻게해줘야하는가? 에대한 문제인데, 위의 방법과 마찬가지로 꽃이 필 개수인 sum(기둥좌표)를 구하고

1. add(기둥위치, -sum(기둥좌표))

2. add(기둥위치, +sum(기둥좌표))

이렇게 해주면 이미 피어있는 꽃에 대한 처리를 해줄 수 있다.