[백준 2934번] LRH 식물 (Python3)

import sys
input = sys.stdin.readline

def update(v,a,b,s,e,x):
  if a==s and b==e:
    seg[x] += v
    return
  mid = (s+e)//2
  if b <= mid:
    update(v,a,b,s,mid,x*2)
  elif a > mid:
    update(v,a,b,mid+1,e,x*2+1)
  else:
    update(v,a,mid,s,mid,x*2)
    update(v,mid+1,b,mid+1,e,x*2+1)

def cal(n,s,e,x):
  if s==e:
    return seg[x]
  mid = (s+e)//2
  if n <= mid:
    return seg[x]+cal(n,s,mid,x*2)
  return seg[x]+cal(n,mid+1,e,x*2+1)

N = 1<<17; seg = [0]*4*N
for _ in range(int(input())):
  i,j = map(int,input().split())
  s1,s2 = cal(i,0,N,1),cal(j,0,N,1)
  print(s1+s2)
  update(-s1,i,i,0,N,1); update(-s2,j,j,0,N,1)
  if j>i+1:
    update(1,i+1,j-1,0,N,1)

세그먼트 트리 응용문제

수열과 쿼리 21 [백준 16975번] 수열과 쿼리 21 (Python3) (tistory.com) 문제와 거의 유사하다.

 

수열과 쿼리 21을 풀었다는 가정하게 풀이를 설명하면,

1. L,R이 입력되면 L의 합과 R의 합을 수열과 쿼리 21 방식으로 구하고 s1,s2로 둔다.

2. 구간 L~L에 -s1을 갱신하고, R~R에 -s2를 갱신하고 L+1~R-1에 1을 갱신한다.

3. s1+s2를 출력한다.

 

레이지 세그먼트 트리를 이용해서 해결할 수도 있는 문제이지만 구간합을 출력하는 문제가 아니라 특정 인덱스의 값을 출력하는 문제이기 때문에 굳이 레이지 세그를 이용할 필요가 없다.

 

 

오늘의 교훈) 다양한 문제를 해결하자