백준 10070 벽

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

 

구간에 min, max를 적용하는 쿼리를 처리하면 된다.

구간 쿼리니까 세그 박고 싶은데 먼가 잘 안 되고..

무지성으로 쓰자니 쿼리 순서에 따라 답이 달라지고..

세그비츠가 비슷한 연산을 지원했던 것 같기도 하고..?

뇌절하지 말자

 

lazy propagation을 설계할 때는 한 정점에 여러 쿼리가 쌓이는 상황을 잘 생각해야 한다.

같은 구간에 적용된 쿼리 중 min 쿼리는 $h$가 최대인 것만, max 쿼리는 $h$가 최소인 것만 고려하면 된다는 점은 자명하다. 고려할 min 쿼리의 $h$를 $min_h$, max 쿼리의 $h$를 $max_h$로 두자.

구간에 적용된 $min_h$ $\le$ $max_h$인 경우는 문제가 되지 않고, 크기가 뒤집히는 경우만 잘 처리하면 된다.

 

어떤 구간에서 쿼리가 여러 번 적용되었고, 그 과정에서 $min_h$와 $max_h$의 크기가 뒤집히는 경우가 생기지 않았다고 생각해 보자. 이는 해당 구간의 모든 수가 $min_h$ 이상 $max_h$ 이하라는 뜻이다. 이때 새로운 max 쿼리의 $h$가 $min_h$보다 작다면 해당 구간의 모든 수가 $h$로 바뀔 것이며, 새로운 min 쿼리의 $h$가 $max_h$보다 큰 경우도 마찬가지이다. 따라서 한 번 크기가 뒤집히는 상황이 생긴다면 $min_h = max_h = h$가 되며, 이후 쿼리가 어떻게 들어오던 $min_h = max_h$를 유지한다. 

 

부모 정점에 쌓인 $Pmin_h, Pmax_h$ 쿼리를 자식 정점으로 전파하는 상황을 생각해 보자. 자식 정점에 쌓인 쿼리가 $min_h, max_h$일 때, 크기가 뒤집히는 경우는 $max_h < Pmin_h$ 또는 $Pmax_h < min_h$인 경우이다. 전파 과정이 정당하다면 $Pmin_h \le Pmax_h$를 만족할 것이므로, 두 경우가 동시에 발생할 수는 없다. 따라서 뒤집히는 경우가 발생한다면 위 문단에서 설명한 것처럼 갱신해주고, 발생하지 않는다면 $min_h$와 $max_h$를 잘 수정해주면 $min_h \le max_h$를 유지하면서 해당 구간에 속한 수의 범위를 잘 갱신해줄 수 있다. 어떤 구간에 쿼리를 적용시키려면 Lazy Propagation의 성질에 의해 이전까지 해당 구간에 뿌려진 모든 쿼리가 먼저 적용되므로 시간 순서가 꼬이는 걱정은 하지 않아도 된다.

 

실제 쿼리를 반영시키는 작업은 리프 노드에서만 수행해도 된다.

 

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
using namespace std;
const int S = 2e6 + 50;
 
int mi[S], lmi[S << 2], lma[S << 2], N, Q;
 
void push(int now, int l, int r){
    if (l == r){
        mi[l] = max(mi[l], lmi[now]);
        mi[l] = min(mi[l], lma[now]);
    }
    else{
        for (int i : {now*2, now*2+1}){
            if (lmi[now] <= lma[i]) lmi[i] = max(lmi[i], lmi[now]);
            else lmi[i] = lma[i] = lmi[now];
            if (lma[now] >= lmi[i]) lma[i] = min(lma[i], lma[now]);
            else lmi[i] = lma[i] = lma[now];
        }
    }
    lmi[now] = 0;
    lma[now] = 1e9;
}
 
void query(int now, int l, int r, int s, int e, int h, int op){
    push(now, l, r);
    if (e < l or r < s) return;
    if (s <= l and r <= e){
        if (op == 1) lmi[now] = h;
        else lma[now] = h;
        push(now, l, r);
        return;
    }
    int mid = l+r >> 1;
    query(now*2, l, mid, s, e, h, op);
    query(now*2+1, mid+1, r, s, e, h, op);
}
 
void run(int now, int l, int r){
    push(now, l, r);
    if (l == r)
        return;
    int mid = l+r >> 1;
    run(now*2, l, mid);
    run(now*2+1, mid+1, r);
}
 
int main() {
    fast;
    
    cin >> N >> Q;
    memset(lma, 0x3f, sizeof lma);
    while (Q--){
        int op, l, r, h;
        cin >> op >> l >> r >> h;
        query(1,1,N,l+1,r+1,h,op);
    }
    run(1, 1, N);
    for (int i = 1; i <= N; i++) cout << mi[i] << '\n';
}