====== 디지털 비디오 디스크(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로 통과시키는 데에 설공. 
    * 새롭게 만든 [[:ps:teflib:segmenttree#MinSegmentTree|teflib.segmenttree.MinSegmentTree]]를 사용해보았다. (RMQ에 최적화된 세그트리 구현..). 이렇게 하자, 굳이 펜윅트리와 세그트리 두개를 같이 쓰지 않더라도, 최댓값 세그트리와 최솟값 세그트리를 사용해서 통과되었다.

===== 코드 =====

==== 코드 1 - 최솟값 세그트리 + 구간합 펜윅트리 ====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]], [[:ps:teflib:segmenttree#SegmentTree|teflib.segmenttree.SegmentTree]]


==== 코드 1 - 최솟값 세그트리 + 최댓값 세그트리 ====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:segmenttree#MinSegmentTree|teflib.segmenttree.MinSegmentTree]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}