[백준/9345] 디지털 비디오 디스크 (DVDs) (Python)

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

9345번: 디지털 비디오 디스크(DVDs)

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:42:50

 

---

 

문제 설명

 

 

최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기있는 N개의 DVD들로 구성된 시리즈를 구매한다(각 DVD들은 0번부터 N-1 까지 이루어져 있다).

ACM 대여점의 주인 원주연 또한 울며 겨자먹기로 인기있는 시리즈물을 구매했고, 진열을 하기 위해 맞춤형 선반을 주문제작 하였다(맟춤제작이기 때문에 선반의 번호 또한 0번부터 N-1 까지 이루어져 있다). 주연이는 매우 정갈한 사람이기 때문에 DVD를 진열할 때 i번 DVD는 i번 선반에 진열을 한다.

이 시리즈의 열렬한 팬인 민호는 주연이네 대여점에 시리즈가 입고되었다는 소식을 듣고 찾아왔다. 시리즈물은 연속으로 봐야 흥미가 안떨어지기 때문에 민호는 L번부터 R번까지의 DVD들을 빌리려고 한다. 민호는 주연이가 매우 정갈한 성격인 것임을 알기에 주연이를 믿고 실제 DVD들의 번호를 확인하지 않고 L번 선반부터 R번 선반까지 존재하는 DVD들을 들고 카운터에 가져왔다.

그러나, 민호는 간과한 사실이 있다. 주연이네 대여점에는 진상 손님인 진일이가 찾아온다는 것이였다. 진일이는 선반 A 에 있는 DVD와 선반 B에 있는 DVD를 서로 바꿔 놓는다. 이러한 진일이의 몰상식한 행동때문에 민호와 같이 주연이를 믿고 DVD의 번호를 확인 안하는 선량한 고객들이 피해를 입는 사례들이 속출하였다. 아무 이유가 없는 묻지마 테러로 인해 가게매출이 떨어질 위기에 처하자 주연이는 진일이가 보일때마다 쫒아 냈지만, 시도때도없이 찾아오는 진일이의 진상짓을 막기에는 역부족이였다.

이러한 주연이를 보고 안타까운 마음이 든 민호는 주연이를 위해 프로그램을 작성하기로 결심을 한다. 의욕이 넘치는 민호의 마음과는 달리 실력이 따라주지 못해 프로그램의 기능은 조촐하기만 하다. 프로그램의 기능은 다음과 같다.

손님이 L번 선반부터 R번 선반까지에 있는 DVD들을 가져 왔을때 실제로 DVD가 L번부터 R번까지 있나 확인을 해 줄 수 있다.
DVD의 순서는 상관이 없다. 예를 들어 손님이 2번 선반부터 4번 선반까지에 있는 DVD를 가져왔을 때 DVD가 2, 3, 4 순서로 진열되어 있건, 4, 2, 3 순서로 진열되어 있건 상관이 없다는 얘기다. 즉 L번부터 R번까지의 DVD가 있으면 된다.
문제의 단순화를위해 고객이 DVD를 빌려가면, 그 즉시 시청한뒤 바로 반납한다고 가정한다. 또한 가져다 놓는 위치는 빌리기 전과 동일하다(4, 3, 2 순서로 진열되어 있었으면 다시 4, 3, 2 순서로 진열한다).

 

 

입력 및 출력

 

입력

 

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. (T ≤ 20 인 자연수)

각각의 테스트 케이스 첫 번째 줄에는 DVD들의 수를 의미하는 정수 N 과 대여점에서 일어나는 사건의 수를 의미하는 정수 K 가 주어진다. (1 ≤ N ≤ 100,000 , 1 ≤ K ≤ 50,000)

이어서 대여점에서 일어나는 사건 K 개가 주어진다. 각각의 줄은 세 정수 Q, A, B 을 포함한다. (Q는 0또는 1이고, 0 ≤ A ≤ B < N )

Q는 0 일때, 진상 손님 진일이가 선반 A의 DVD와 선반 B의 DVD를 서로 바꿔 끼우는 사건을 의미한다. 

Q가 1 일때는 손님이 선반 A부터 선반 B에 있는 DVD를 카운터에 가져오는 사건을 의미한다. 위에서도 언급했듯이 이 사건이 DVD들의 위치를 바꾸는 일은 일어나지 않는다.

 

출력

 

손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하고, 그렇지 않다면 "NO"를 출력한다.

 

입력 예시

 

2
5 8
1 0 4
1 1 2
0 1 3
1 2 2
1 1 3
1 0 0
1 0 2
1 2 4
5 5
0 1 2
0 2 3
0 1 3
1 0 1
1 0 2

 

출력 예시

 

YES
YES
YES
YES
YES
NO
NO
YES
NO

 

 

---

 

풀이

 

우선 구성을 보자. 정수 L ~ R 구간에 L ~ R이 전부 존재한다면, 그 구간의 최댓값은 R, 최솟값은 L임이 보장된다. 이는 필요충분조건이다. [L, R] 구간에 [L, R]에 속하지 않은 정수 i가 치환되었다고 가정하면, [L, R] 에 본래 [L, R] 정수 모두가 포함되어있으므로 i는 L보다 작거나 R보다 클 것이다. 즉 최댓값, 최솟값 조건에 모순이 된다.

 

즉 구간 최댓값, 구간 최솟값을 동시에 계산하는 세그먼트 트리를 구현하는 것이 핵심이다.

 

두번째로, 파이썬의 느린 실행속도로는 이 문제의 시간 여유를 풀기 힘들다. 즉 기존의 재귀 세그먼트 트리를 비재귀 세그먼트 트리로 바꾸어 주어야 하는데.... 재귀가 idx = 1인 탑다운 방식으로 표현했다면, 비재귀는 idx가 각 리프 노드인 바텀업 방식으로 구현하는 것이 핵심이었다. (구글링은 역시 신이야!)

 

간단한 구간합 세그먼트 트리를 작성한다고 가정하고, 비재귀 세그먼트 트리의 구현법을 기록해 본다.

• 초기화는 리프 노드를 초기화하고, 리프 노드가 아닌 노드에 대해 차례대로 왼쪽 및 오른쪽 노드를 참조한다.

N = 리프 노드의 최대 크기. 2의 거듭제곱 꼴로 나타난다

for i in range(N, 2*N) : # 리프 노드 초기화
  tree[N+i] = node[i]
for i in range(N-1, 0, -1) : # 중간 노드 초기화
  tree[i] = tree[i<<1] + tree[i<<1|1]
   	# i << 1 = i * 2
    # i << 1 | 1 = i * 2 + 1

 

• 업데이트는 리프 노드를 변경하고, 초기화와 같이 루트 노드로 업데이트한다.

N = 리프 노드의 최대 크기. 2의 거듭제곱 꼴로 나타난다
idx = 바꿀 인덱스, 0 <= idx < N 꼴이다
val = 바꿀 값

idx += N
tree[idx] = val

while idx > 1 : # 루트 노드에 도달할 때까지
  idx >>= 1 # idx //= 2
  tree[idx] = tree[idx<<1] + tree[idx<<1|1] #노드값 갱신

 

• 쿼리(검색)은 머리를 써야 한다.
  • 앞서 초기화와 수정을 진행할 때 관찰할 수 있는 사실로, 어떤 노드에 포함되는 왼쪽 자식 노드는 인덱스가 무조건 짝수, 오른쪽 노드는 인덱스가 무조건 홀수이다.
  • 즉 왼쪽 인덱스가 홀수라면, 왼쪽 인덱스는 상위 노드에 포함되지 않는다. 즉 바로 값을 반영해주고 왼쪽 인덱스에 1을 더해 짝수로 맞추어 주어야 한다.
  • 반대로 오른쪽 인덱스가 짝수라면, 오른쪽 인덱스는 상위 노드에 포함되지 않는다. 이 역시 값 반영 및 1을 빼 주어 홀수로 맞추어 주어야 한다.
  • 왼쪽과 오른쪽 인덱스를 상위 노드로 증가시킨다( >>= 1, //= 2)
  • 만약 왼쪽, 오른쪽 인덱스가 교차한다면(>) 탐색을 중지해도 된다.

N = 리프 노드의 최대 크기. 2의 거듭제곱 꼴로 나타난다
lidx, ridx = 왼쪽과 오른쪽 인덱스, 0 <= lidx <= ridx < N 꼴이다
ret = 0 # 우리가 구하는 구간합값.

while lidx <= ridx :
  if lidx % 2 == 1 : # 왼쪽 인덱스가 홀수라면
    ret += self.tree[lidx] # 바로 값 반영 후
    lidx += 1 # 1 증가
  if ridx % 2 == 0 : # 오른쪽 인덱스가 짝수라면
    ret += self.tree[ridx]
    ridx -= 1
  lidx >>= 1
  ridx >>= 1

 

이를 min, max 세그먼트 트리로 바꾸는 것은 어렵지 않으니, 한 번 도전해보자!

 

풀이 코드

import sys
import math
input = sys.stdin.readline

class SegTree :
  def __init__(self, N) :
    self.sz = 1 << math.ceil(math.log2(N))
    self.tree = [[0, 0] for _ in range(2*self.sz)]
    
    for i in range(self.sz) :
      if i < N :
        self.tree[i + self.sz] = [i, i]
      else :
        self.tree[i + self.sz] = [self.sz, -1]
    for i in range(self.sz-1, 0, -1) :
      self.tree[i][0] = min(self.tree[i<<1][0], self.tree[i<<1|1][0])
      self.tree[i][1] = max(self.tree[i<<1][1], self.tree[i<<1|1][1])

  def search(self, left, right) :
    left += self.sz
    right += self.sz
    ret = [self.sz, -1]
    while left <= right :
      if left % 2 == 1 :
        ret[0] = min(ret[0], self.tree[left][0])
        ret[1] = max(ret[1], self.tree[left][1])
        left += 1
      if right % 2 == 0 :
        ret[0] = min(ret[0], self.tree[right][0])
        ret[1] = max(ret[1], self.tree[right][1])
        right -= 1
      left >>= 1
      right >>= 1
    return ret
    
  def update(self, aidx, bidx) :
    aidx += self.sz
    bidx += self.sz
    def _update(idx) :
      while idx > 1 :
        idx >>= 1
        self.tree[idx][0] = min(self.tree[idx<<1][0], self.tree[idx<<1|1][0])
        self.tree[idx][1] = max(self.tree[idx<<1][1], self.tree[idx<<1|1][1])
    for i in range(2) :
      self.tree[aidx][i], self.tree[bidx][i] = self.tree[bidx][i], self.tree[aidx][i]
    _update(aidx)
    _update(bidx)

def solve() :
  N, K = map(int, input().split())
  tree = SegTree(N)
  for _ in range(K) :
    q, a, b = map(int, input().split())
    if q == 0 :
      tree.update(a, b)
    else :
      aval, bval = tree.search(a, b)
      if aval == a and bval == b :
        print("YES")
      else :
        print("NO")

for _ in range(int(input())) :
  solve()