백준 10070번: 벽 [C++]

작성일 | In
다이아몬드 V 다이아몬드 V

문제

벽
서로 다른 두 쿼리(min, max)를 처리하는 문제입니다.

풀이

세그먼트 트리의 노드에 각 구간에 적용될 min, max쿼리를 저장해둡니다.
그리고 이 쿼리 값(height)들을 minLazy, maxLazy라고 합시다.

maxLazy < minLazy일 때 쿼리의 적용 순서가 관계없음을 이용해야 이 문제를 풀 수 있습니다. 관계없는 이유는 여담에서 증명해 보이겠습니다.

모든 노드는 초깃값으로 maxLazy = 0, minLazy = INF를 갖습니다.
어떤 노드가 maxLazy < minLazy를 만족한다고 합시다.
max쿼리로 max값이 들어오게 되면

  1. max < maxLazy인 경우
    아무 영향도 주지 않습니다. 따라서 무시합니다.
  2. maxLazy < max < minLazy인 경우
    maxLazy = max로 값을 바꿔줍니다.
  3. minLazy < max인 경우
    maxLazy = max로, minLazy = INF로 바꿔줍니다.

위 과정을 다르게 쓰면
maxLazy = max(maxLazy, max)
minLazy = max(minLazy, max)
입니다.

같은 방식으로 min쿼리가 들어오면
maxLazy = min(maxLazy, min)
minLazy = min(minLazy, min)
입니다.

어떤 쿼리가 들어오든 항상 maxLazy < minLazy임을 알 수 있습니다.

1
2
3
4
5
6
7
8
9
void update(int node, int query, int value) {
    if (query == 1) {
        tree[node].maxLazy = max(tree[node].maxLazy, value);
        tree[node].minLazy = max(tree[node].minLazy, value);
    } else {
        tree[node].maxLazy = min(tree[node].maxLazy, value);
        tree[node].minLazy = min(tree[node].minLazy, value);
    }
}

lazy값을 자식으로 전파할 때는 순서 상관없이 전파해 주면 됩니다. 항상 maxLazy < minLazy이기 때문에 순서를 신경쓰지 않아도 됩니다.

1
2
3
4
5
6
7
8
9
10
11
void propagate(int node, int start, int end) {
    if (start != end) {
        update(node*2, 1, tree[node].maxLazy);
        update(node*2, 2, tree[node].minLazy);
        update(node*2+1, 1, tree[node].maxLazy);
        update(node*2+1, 2, tree[node].minLazy);

        tree[node].maxLazy = 0;
        tree[node].minLazy = INF;
    }
}

모든 쿼리가 끝나고, 벽의 값을 찾을 때는 리프노드의 maxLazy값을 찾으면 됩니다.
min(max(0, maxLazy), minLazy) = maxLazy이기 때문입니다.

1
2
3
4
5
6
7
8
9
int getValue(int node, int start, int end, int index) {
    propagate(node, start, end);
    if (start == end) return tree[node].maxLazy;
    if (index <= (start+end)/2) {
        return getValue(node*2, start, (start+end)/2, index);
    } else {
        return getValue(node*2+1, (start+end)/2+1, end, index);
    }
}

이외에는 다른 느리게 갱신되는 세그먼트 트리처럼 구현해주면 됩니다.

코드

Node클래스와 Wall클래스를 만들었습니다. 세그먼트 트리인 Wall클래스의 private부분을 보시면 됩니다.

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
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;

void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const int INF = 100000;


class Node {
public:
    int maxLazy, minLazy;

    Node() {
        maxLazy = 0;
        minLazy = 0;
    }
};


class Wall {
private:
    vector<Node> tree;
    int wallSize;

    void update(int node, int query, int value) {
        if (query == 1) {
            tree[node].maxLazy = max(tree[node].maxLazy, value);
            tree[node].minLazy = max(tree[node].minLazy, value);
        } else {
            tree[node].maxLazy = min(tree[node].maxLazy, value);
            tree[node].minLazy = min(tree[node].minLazy, value);
        }
    }


    void propagate(int node, int start, int end) {
        if (start != end) {
            update(node*2, 1, tree[node].maxLazy);
            update(node*2, 2, tree[node].minLazy);
            update(node*2+1, 1, tree[node].maxLazy);
            update(node*2+1, 2, tree[node].minLazy);

            tree[node].maxLazy = 0;
            tree[node].minLazy = INF;
        }
    }


    void rangeUpdate(int node, int start, int end, int left, int right, int query, int value) {
        propagate(node, start, end);
        if (right < start or end < left) return;
        if (left <= start and end <= right) {
            update(node, query, value);
            return;
        }
        rangeUpdate(node*2, start, (start+end)/2, left, right, query, value);
        rangeUpdate(node*2+1, (start+end)/2+1, end, left, right, query, value);
        // 자식에게 전달된 쿼리는 부모에게 영향을 주지 않으므로 노드의 병합 없이 함수를 끝냅니다.
    }


    int getValue(int node, int start, int end, int index) {
        propagate(node, start, end);
        if (start == end) return tree[node].maxLazy;
        if (index <= (start+end)/2) {
            return getValue(node*2, start, (start+end)/2, index);
        } else {
            return getValue(node*2+1, (start+end)/2+1, end, index);
        }
    }

public:
    Wall(int wallSize) : wallSize(wallSize) {
        int height = (int) ceil(log2(wallSize));
        tree.resize(1 << (height + 1), Node());
    }

    void buildWall(int left, int right, int op, int height) {
        rangeUpdate(1, 0, wallSize-1, left, right, op, height);
    }

    int getWallHeight(int pos) {
        return getValue(1, 0, wallSize-1, pos);
    }
};


int main() {
    fastio();

    int n, k;
    cin >> n >> k;

    Wall wall(n);

    while (k--) {
        int op, left, right, height;
        cin >> op >> left >> right >> height;

        wall.buildWall(left, right, op, height);
    }

    for (int i = 0; i < n; i++) {
        cout << wall.getWallHeight(i) << '\n';
    }

    return 0;
}

여담

maxLazy < minLazy일 때 쿼리의 적용 순서가 관계없음을 증명해 보겠습니다.
쿼리를 적용하기 전의 벽의 높이가 height였다고 합시다.

max(min(height, minLazy), maxLazy)와
min(max(height, maxLazy), minLazy)의 값이 같은지 보면 됩니다.

  1. height < maxLazy인 경우
    max(height, maxLazy) = maxLazy min(maxLazy, minLazy) = maxLazy

따라서 height = 0일 때 maxLazy인 이유를 알 수 있습니다. 2. maxlazy < height < minLazy인 경우 max(height, maxLazy) = height min(height, minLazy) = height 3. minLazy < height인 경우 max(minLazy, maxLazy) = minLazy min(height, minLazy) = minLazy

따라서 maxLazy < minLazy이면 쿼리의 적용 순서는 상관이 없습니다.

백준 10070번: 벽 [C++]