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

• 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에 최적화된 세그트리 구현..). 이렇게 하자, 굳이 펜윅트리와 세그트리 두개를 같이 쓰지 않더라도, 최댓값 세그트리와 최솟값 세그트리를 사용해서 통과되었다.

"""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()

• Dependency: teflib.fenwicktree.FenwickTree, teflib.segmenttree.SegmentTree

"""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()

• Dependency: teflib.segmenttree.MinSegmentTree