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

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (69/187)
  • 꽉찬 자연수 집합에서 Swap만 허용하면, Min과 Max가 같을때 수의 구성은 항상 같다.
    • 예를들면 1~10까지 꽉 찬 자연수 집합을 생각해보자
    • 아무리 Swap해도 1,2,3,4,5안에서만 swap하면 min과 max가 바뀌지 않는다.
    • 이때 1,2,3,4,5밖에서 7같은거를 3과 바꾼다면 max가 바뀌게 된다.
  • 이를 이용해서 min, max segTree를 만들면 쿼리당 로그시간에 해결 가능
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

#include <sys/stat.h>
#include <sys/mman.h>
class fio {
  size_t rsize;
  unsigned char* rbuf;
  int ridx;

  public:
  fio() : ridx(0) {
    struct stat rstat;
    fstat(0, &rstat);
    rsize = rstat.st_size;
    rbuf = (unsigned char*)mmap(0,rsize,PROT_READ,MAP_FILE|MAP_PRIVATE,0,0);
  }

  inline bool isBlank() {
    return
      rbuf[ridx] == '\n' || rbuf[ridx] == '\t' || rbuf[ridx] == '\r' ||
      rbuf[ridx] == '\f' || rbuf[ridx] == '\v' || rbuf[ridx] == ' ';
  }
  inline void consumeBlank() { while (isBlank()) ridx++; }

  inline int readInt(){
    int res = 0, flag = 0;
    consumeBlank();
    if (rbuf[ridx] == '-'){
      flag = 1;
      ridx++;
    }
    while (!isBlank() && ridx < rsize)
      res = 10 * res + rbuf[ridx++] - '0';
    return flag ? -res : res;
  }
};

const int MAX = 0, MIN = 1;
int maxTree[200009];
int minTree[200009];

inline int myMax(int a, int b) {return a > b ? a: b; }
inline int myMin(int a, int b) {return a < b ? a: b; }

class SegmentTree {
  int N, INIT, *tree;
  decltype(myMax)* cb;

public:
  SegmentTree(int& n, int type, int init): N(n), INIT(init) {
    cb = (type ? myMin : myMax);
    tree = (type ? minTree : maxTree);
    for(int i = N; i < 2*N; i++)
      tree[i] = i-N;
    for(int i = N-1; i > 0; i--)
      tree[i] = cb(tree[2*i], tree[2*i+1]);
  }

  void update(int a, int b) {
    a += N, b += N;
    swap(tree[a], tree[b]);
    for(int p = a; p > 1; p /= 2)
      tree[p/2] = cb(tree[p], tree[p^1]);
    for(int p = b; p > 1; p /= 2)
      tree[p/2] = cb(tree[p], tree[p^1]);
  }

  int query(int l, int r) {
    int res = INIT;
    for(l += N, r += N; l < r; l /= 2, r /= 2) {
      if(l&1) res = cb(res, tree[l++]);
      if(r&1) res = cb(res, tree[--r]);
    }
    return res;
  }
};

fio io;
int main() {
  ios::sync_with_stdio(false);
  int TC, N, K, Q, A, B;
  TC = io.readInt();
  while(TC--) {
    N = io.readInt();
    K = io.readInt();
    SegmentTree maxSeg(N, MAX, 0);
    SegmentTree minSeg(N, MIN, INT_MAX);

    for(int i = 0; i < K; i++) {
      Q = io.readInt();
      A = io.readInt();
      B = io.readInt();
      if(Q == 0) {
        maxSeg.update(A, B);
        minSeg.update(A, B);
      } else {
        int a = minSeg.query(A, B+1);
        int b = maxSeg.query(A, B+1);
        printf(a == A && b == B ? "YES\n" : "NO\n");
      }
    }
  }
}