[백준/2934] LRH 식물 (Python)

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

2934번: LRH 식물

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:20:41

 

---

 

문제 설명

 

 

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다.

상근이는 매일 매일 화단에 식물을 하나씩 심는다. 첫 번째 날에 심은 식물의 높이는 1이고, 그 다음날에 심은 식물은 전날에 심은 식물의 높이보다 1 크다.

새 식물의 줄기가 다른 식물의 수평 선분과 교차하는 경우가 있다. 이러한 경우에 그 위치에는 꽃이 하나 피게 된다. (이미 꽃이 있는 경우에는 꽃이 더 피지 않는다) 점에서 접하는 경우에는 꽃이 피지 않는다.

아래 그림은 예제를 나타낸 것이다.

모든 식물의 좌표가 주어졌을 때, 매일 매일 피는 꽃의 개수를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 식물을 심은 날의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개 줄에는 매일 매일 심은 식물의 두 줄기 좌표 L과 R이 주어진다. (1 ≤ L < R ≤ 100,000) 

 

출력

 

총 N개의 줄에 매일 매일 핀 꽃의 수를 출력한다.

 

입력 예시

 

4
1 4
3 7
1 6
2 6

 

출력 예시

 

0
1
1
2

 

 

---

 

풀이

 

n번째의 구간 [L, R]의 식물이 심어진다고 가정하자. 그렇다면 꽃이 필 수 있는 경우는 L, R의 수직선이 각각 이전에 그어진 수평선 중 아직 쓰이지 않은 수평선과 만날 때이다. 즉

 

• search(x) : x에 저장된, 아직 만나지 않은 수평선의 개수을 출력. 그 후 모든 만나지 않은 직선을 만난 셈이므로 0으로 초기화
• update(l, r) : l, r구간에 수평선이 지나므로 l, r구간에 1을 추가

두 가지 기능을 수행한다고 볼 수 있다. 구간 [L, R]의 경우 (search(L) + search(R)값을 출력하고, 동시에 update(L+1, R-1)로 업데이트해줄 필요가 있다. 구간 업데이트를 O(logN)으로 수행 가능한 lazy segment tree를 사용해봄직하다.

 

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = 10**5

N = int(input())
tree = [0]*(4*MAX+4)
lazy = [0]*(4*MAX+4)

def propagate(start, end, idx) :
  if start != end :
    lazy[idx*2] += lazy[idx]
    lazy[idx*2+1] += lazy[idx]
  else :
    tree[idx] += lazy[idx]
  lazy[idx] = 0

def update(l, r, start=0, end=MAX, idx=1) :
  if l > r :
    return
  propagate(start, end, idx)
  if l > end or r < start :
    return
  if l <= start <= end <= r :
    lazy[idx] += 1
    propagate(start, end, idx)
    return
  mid = (start + end) // 2
  update(l, r, start, mid, idx*2)
  update(l, r, mid+1, end, idx*2+1)

def search(target) :
  start, end, idx = 0, MAX, 1
  while start < end :
    propagate(start, end, idx)
    mid = (start + end) // 2
    if target <= mid :
      end = mid
      idx = idx*2
    else :
      start = mid+1
      idx = idx*2+1
  propagate(start, end, idx)
  result = tree[idx] 
  tree[idx] = 0
  return result

for _ in range(N) :
  L, R = map(int, input().split())
  print(search(L) + search(R))
  update(L+1, R-1)

풀이 완료!