백준9345 디지털 비디오 디스크(DVDs)

작성일 | In

문제 링크

  • http://icpc.me/9345

문제 출처

  • 2013 ACM-ICPC Thailand G번

사용 알고리즘

  • Segment Tree

시간복잡도

  • 각 테스트케이스 별로 O(m log n)

풀이

이 문제는 두 가지 쿼리가 주어집니다.

  1. A번째 DVD, B번째 DVD swap
  2. A~B DVD가 존재하는지 확인 (순서는 상관 없다.)

이 문제는 구간의 최댓값과 최솟값을 모두 구해준 뒤, 최솟값이 A와 같은지와 최댓값이 B와 같은지만 비교해주면 됩니다.

Min Segment Tree와 Max Segment Tree를 따로 구현하면 코드가 길어지기 때문에 두 개를 한 번에 구해주는 Segment Tree를 만들어서 문제를 풀도록 하겠습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
struct MinMaxSeg{
	vector<int> Max, Min;
	int size;

	MinMaxSeg(int s) : size(s) {
		Max.resize(4*s, 0), Min.resize(4*s, 0);
	}

	void init(int node, int start, int end){
		if(start == end){
			Min[node] = Max[node] = start; return;
		}

		int mid = (start+end) >> 1;
		init(node*2, start, mid), init(node*2+1, mid+1, end);

		Min[node] = min(Min[node*2], Min[node*2+1]);
		Max[node] = max(Max[node*2], Max[node*2+1]);
	}

	void init(){
		init(1, 0, size-1);
	}

	void update(int node, int start, int end, int idx, int val){
		if(idx < start || end < idx) return;
		if(start == end){
			Min[node] = Max[node] = val; return;
		}

		int mid = (start+end) >> 1;
		update(node*2, start, mid, idx, val), update(node*2+1, mid+1, end, idx, val);

		Min[node] = min(Min[node*2], Min[node*2+1]);
		Max[node] = max(Max[node*2], Max[node*2+1]);
	}

	void update(int val, int idx){
		update(1, 0, size-1, idx, val);
	}

	p get(int node, int start, int end, int left, int right){
		if(right < start || end < left) return {1e9+7, 0};
		if(left<=start && end<=right) return {Min[node], Max[node]};

		int mid = (start+end) >> 1;
		p i = get(node*2, start, mid, left, right);
		p j = get(node*2+1, mid+1, end, left, right);
		return {min(i.first, j.first), max(i.second, j.second)};
	}

	p get(int left, int right){
		return get(1, 0, size-1, left, right);
	}

};

void solve(){
    int n, m; cin >> n >> m;
    MinMaxSeg tree(n);
    tree.init();

    while(m--){
        int q, a, b; cin >> q >> a >> b;
        if(q){
            auto tmp = tree.get(a, b);
            if(tmp.first == a && tmp.second == b) cout << "YES\n";
            else cout << "NO\n";
        }else{
            auto i = tree.get(a, a);
            auto j = tree.get(b, b);
            tree.update(j.first, a);
            tree.update(i.first, b);
        }
    }
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--){
		solve();
	}
}