백준16910 mex와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/16910

사용 알고리즘

  • 세그 레이지

시간복잡도

  • $O(N log N)$

풀이

세그먼트 트리를 이용해 존재하지 않는 가장 작은 원소는 쉽게 구할 수 있습니다.
수 i의 존재 여부를 i번째 리프노드에 저장하고, 구간합을 구하는 세그먼트 트리를 이용하면 할 수 있습니다.
그러므로 1번 쿼리는 [l, r] 구간을 1로 변경하는 쿼리, 2번 쿼리는 0으로 변경하는 쿼리, 3번 쿼리는 tree[node] = (e-s+1) - tree[node] 같은 형태로 변경하는 쿼리로 처리할 수 있습니다.

쿼리의 범위가 10^18이지만 좌표압축을 해주면 $O(N)$으로 줄여줄 수 있습니다. 모든 구간 [l, r]에 대해서 l, r+1만 저장해도 되지만, 저는 구현의 편의를 위해 l-1, l, l+1, r-1, r, r+1 총 6개를 넣었습니다.
레이지만 잘 처리해주면 쉽게 풀 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n;
vector<ll> comp;
ll op[101010], l[101010], r[101010];

int tree[1 << 21];
int tmp1[1 << 21]; //sum
int tmp2[1 << 21]; //xor

void push(int node, int s, int e){
    if(tmp1[node] == -1 && tmp2[node] == 0) return;
    if(tmp1[node] != -1){
        tree[node] = tmp1[node] * (e-s+1);
        if(s ^ e) for(auto ch : {node << 1, node << 1 | 1}){
            tmp1[ch] = tmp1[node];
            tmp2[ch] = 0;
        }
        tmp1[node] = -1;
    }
    if(tmp2[node]){
        tree[node] = (e-s+1) - tree[node];
        if(s ^ e) for(auto ch : {node << 1, node << 1 | 1}){
            if(tmp1[ch] == -1) tmp2[ch] ^= 1;
            else tmp1[ch] ^= 1, tmp2[ch] = 0;
        }
        tmp2[node] = 0;
    }
}

void update(int node, int s, int e, int l, int r, int v){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        tmp1[node] = v; push(node, s, e);
        return;
    }
    int m = s + e >> 1;
    update(node << 1, s, m, l, r, v); update(node << 1 | 1, m+1, e, l, r, v);
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

void update(int node, int s, int e, int l, int r){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        tmp2[node] = 1; push(node, s, e);
        return;
    }
    int m = s + e >> 1;
    update(node << 1, s, m, l, r); update(node << 1 | 1, m+1, e, l, r);
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

int query(int node, int s, int e){
    push(node, s, e);
    if(s == e) return s;
    int m = s + e >> 1;
    push(node << 1, s, m);
    push(node << 1 | 1, m+1, e);
    if(tree[node << 1] < m - s + 1) return query(node << 1, s, m);
    else return query(node << 1 | 1, m+1, e);
}

int query(int node, int s, int e, int x){
    push(node, s, e);
    if(s == e) return tree[node];
    int m = s + e >> 1;
    if(x <= m) return query(node << 1, s, m);
    else return query(node << 1 | 1, m+1, e);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n; comp.reserve(n * 6 + 1);
    comp.push_back(1);
    for(int i=1; i<=n; i++){
        cin >> op[i] >> l[i] >> r[i];
        for(int j=-1; j<=1; j++){
            if(l[i]+j > 0) comp.push_back(l[i] + j);
            if(r[i]+j > 0) comp.push_back(r[i] + j);
        }
    }
    memset(tmp1, -1, sizeof tmp1);
    compress(comp);
    for(int i=1; i<=n; i++){
        int a = lower_bound(all(comp), l[i]) - comp.begin();
        int b = lower_bound(all(comp), r[i]) - comp.begin();
        if(op[i] == 1) update(1, 0, comp.size(), a, b, 1);
        if(op[i] == 2) update(1, 0, comp.size(), a, b, 0);
        if(op[i] == 3) update(1, 0, comp.size(), a, b);
        cout << comp[query(1, 0, comp.size())] << "\n";
    }
}