10070번: 벽

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


$O((k+n)\lg n)$

본 문제를 세그먼트 트리에서 lazy propagation을 이용하여 해결할 수 있도록 결합법칙이 성립하는 연산 @를 정의해보자.

트리의 각 노드는 (low,up)을 가지는데 이것은 해당 구간의 벽 높이가 [low,up] 범위 안이라는 의미이다.
s1=[l1,u1], s2=[l2,r2]일 때 s1 @ s2 는
u1<l2이면 [l1,l1]
r2<l1이면 [r2,r2]
그 이외 $s1 \cap s2$
라고 정의하자. 이 때, 연산 순서는 자식 @ 부모 방향이다.
이렇게 정의한 연산은 결합 법칙이 성립한다. 즉, (A@B)@C = A@(B@C)
이제 lazy propagation을 이용할 수 있다.
op=1이면 [h,inf]를 @시켜주고
op=2이면 [0,h]를 @시켜준다.
최종 답은 리프노드부터 루트노드까지 @시켜주면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 2e6, inf = 1e5;
int n, k;
struct st {
    int low, up;
    st operator+(st i) {
        return{ min(max(low,i.low),i.up),min(max(up,i.low),i.up) };
    }
}tree[MXN * 4];
void update(int h, int l, int r, int gl, int gr, st x) {
    if (r < gl || gr < l) return;
    if (l^r) {
        tree[h * 2 + 1] = tree[h * 2 + 1] + tree[h];
        tree[h * 2 + 2] = tree[h * 2 + 2] + tree[h];
        tree[h] = { 0,inf };
    }
    if (gl <= l&&r <= gr) tree[h] = tree[h] + x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
}
st query(int h, int l, int r, int g) {
    if (r < g || g < l) return{ 0,inf };
    if (l == r) return tree[h];
    return query(h * 2 + 1, l, (l + r) / 2, g) + query(h * 2 + 2, (l + r) / 2 + 1, r, g) + tree[h];
}
int main() {
    for (scanf("%d%d", &n, &k); k--;) {
        int op, l, r, h;
        scanf("%d%d%d%d", &op, &l, &r, &h);
        if (op == 1) update(0, 0, n - 1, l, r, { h, inf });
        else update(0, 0, n - 1, l, r, { 0,h });
    }
    for (int i = 0; i < n; i++) printf("%d\n", query(0, 0, n - 1, i).up);
    return 0;
}