사용자 도구

사이트 도구


ps:problems:boj:9345

디지털 비디오 디스크(DVDs)

ps
링크acmicpc.net/…
출처BOJ
문제 번호9345
문제명디지털 비디오 디스크(DVDs)
레벨플래티넘 3
분류

구간 쿼리

시간복잡도O(n+qlogn)
인풋사이즈n<=100,000, q<=50,000
사용한 언어Python
제출기록51920KB / 7240ms
최고기록7240ms
해결날짜2022/06/29
태그

[단계별]38단계, [라이]세그먼트 트리

풀이

  • n개의 서로 다른 수가 있을 때, 이 수들이 x, x+1, …, x+n-1 인지를 확인하는 방법은 일일히 정렬해서 비교해볼 필요 없이, 그냥 최댓값이 x+n-1이고 최솟값이 x인지만 확인해보면 된다.
  • 이 아이디어를 이 문제에 그대로 적용하면, 구간에 있는 DVD번호가 A, A+1, …, B인지를 확인하려면, 구간의 최댓값과 최솟값만을 계산할 수 있으면 된다. 그것은 세그먼트 트리로 O(logn)에 가능하다.
  • 위치를 바꾸는 것은 두번의 포인트 업데이트 쿼리. 카운터에 가져온 DVD를 확인하는 것은 구간 최솟값과 구간 최댓값 쿼리가 필요하다. 모두 O(logn)에 가능하므로, 쿼리를 처리하는 데에는 총 O(qlogn)의 시간 복잡도. 그리고 처음에 세그먼트 트리를 구축하는데에도 O(n)이 걸리므로 모두 합치면 O(n+qlogn)이다
  • 원래 (최솟값,최댓값)의 튜플을 저장하는 세그먼트 트리로 구현했었는데 시간이 빡빡했다. Python으로는 시간 초과, PyPy를 써서 겨우 1800ms 정도에 통과.. 코드가 덜 깔끔하긴 하지만 튜플을 쓰지 않고, 최솟값을 저장하는 세그트리와 최댓값을 저장하는 세그트리로 나눠서 구현했더니 시간이 200~300ms 정도로 단축되었다.
  • 여기서 더 나아가서, 최댓값과 최솟값 대신에, 최솟값과 합을 이용해서 체크하는 것으로 로직을 바꿨다. 이렇게 해도 n개의 수가 조건을 만족하는지 체크는 가능하고, 합은 펜윅트리를 쓸수 있으니까 조금 더 빨라진다. 최솟값 세그트리와 합 펜윅트리를 이용해서 구현한 결과 아슬아슬하게 7452ms로 통과시키는 데에 설공.
    • 새롭게 만든 teflib.segmenttree.MinSegmentTree를 사용해보았다. (RMQ에 최적화된 세그트리 구현..). 이렇게 하자, 굳이 펜윅트리와 세그트리 두개를 같이 쓰지 않더라도, 최댓값 세그트리와 최솟값 세그트리를 사용해서 통과되었다.

코드

코드 1 - 최솟값 세그트리 + 구간합 펜윅트리

"""Solution code for "BOJ 9345. 디지털 비디오 디스크(DVDs)".

- Problem link: https://www.acmicpc.net/problem/9345
- Solution link: http://www.teferi.net/ps/problems/boj/9345
"""

import sys
from teflib import fenwicktree
from teflib import segmenttree


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, K = [int(x) for x in sys.stdin.readline().split()]
        min_segtree = segmenttree.SegmentTree(range(N), merge=min)
        fenwick_tree = fenwicktree.FenwickTree(range(N))
        dvd_by_pos = list(range(N))
        for _ in range(K):
            Q, A, B = [int(x) for x in sys.stdin.readline().split()]
            if Q == 0:
                dvd_at_a, dvd_at_b = dvd_by_pos[A], dvd_by_pos[B]
                min_segtree.set(A, dvd_at_b)
                min_segtree.set(B, dvd_at_a)
                fenwick_tree.set(A, dvd_at_b)
                fenwick_tree.set(B, dvd_at_a)
                dvd_by_pos[A], dvd_by_pos[B] = dvd_at_b, dvd_at_a
            else:
                s = (A + B) * (B - A + 1) // 2
                if (fenwick_tree.query(A, B + 1) == s and
                        min_segtree.query(A, B + 1) == A):
                    print('YES')
                else:
                    print('NO')


if __name__ == '__main__':
    main()

코드 1 - 최솟값 세그트리 + 최댓값 세그트리

"""Solution code for "BOJ 9345. 디지털 비디오 디스크(DVDs)".

- Problem link: https://www.acmicpc.net/problem/9345
- Solution link: http://www.teferi.net/ps/problems/boj/9345
"""

import sys
from teflib import segmenttree


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, K = [int(x) for x in sys.stdin.readline().split()]
        min_segtree = segmenttree.MinSegmentTree(range(N))
        max_segtree = segmenttree.MinSegmentTree(range(0, -N, -1))
        dvd_by_pos = list(range(N))
        for _ in range(K):
            Q, A, B = [int(x) for x in sys.stdin.readline().split()]
            if Q == 0:
                dvd_at_a, dvd_at_b = dvd_by_pos[A], dvd_by_pos[B]
                min_segtree.set(A, dvd_at_b)
                min_segtree.set(B, dvd_at_a)
                max_segtree.set(A, -dvd_at_b)
                max_segtree.set(B, -dvd_at_a)
                dvd_by_pos[A], dvd_by_pos[B] = dvd_at_b, dvd_at_a
            else:
                if (-max_segtree.query(A, B + 1) == B and
                        min_segtree.query(A, B + 1) == A):
                    print('YES')
                else:
                    print('NO')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q P L T T
 
ps/problems/boj/9345.txt · 마지막으로 수정됨: 2022/07/26 17:41 저자 teferi