BOJ 10070 - 벽 (D5)

사용 알고리즘

segment tree + lazy propagation

 

풀이

뭔가 쉬워보이긴 한데 해보면 바로 해결되지는 않는 그런 문제이다.

세그먼트 트리의 각 노드는 그 노드가 담당하는 구간의 수 범위를 저장한다. 이제 얘를 어떻게 업데이트하고 전파할지가 문제이다.

업데이트할 노드의 원래 수 범위가 [L,R]이고 업데이트할 값이 X라 하자.

일단 이 노드가 업데이트할 구간에 완전히 포함되는 경우를 보자.

op = 1의 경우는 L = max(L,X), R = max(R,X)로 하면 된다.

마찬가지로 op = 2는 L = min(L,X), R = min(R,X)로 하면 된다.

업데이트할 구간에 걸치면, 자식 노드들을 봐야하는데 이때 원래 자식 노드들의 [L,R]과 현재 노드의 [L,R]을 비교해서 자식 노드 [L,R]이 현재 노드에 포함되게 해줘야 한다. 쉽게 말해서 propagate를 업데이트할때 안하고 여기서 하는 것이다.

마찬가지로 query할때도 propagate를 해줘야 한다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
#include <ctime>
#include <random>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000009
typedef long long ll;
ll n, k;
struct segtree{
    struct node{
        ll L=0, R=0;
    };
    vector<node> tree;
    segtree(): tree(8080808){}
    void upd(ll node, ll s, ll e, ll l, ll r, ll diff, ll op){
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            if(op==1){
                tree[node].L = max(tree[node].L,diff);
                tree[node].R = max(tree[node].R,diff);
            }
            else{
                tree[node].L = min(tree[node].L,diff);
                tree[node].R = min(tree[node].R,diff);
            }
            return;
        }
        ll mid = s+e>>1;
        //자식 노드가 부모 노드에 포함되게 하는 과정
        tree[node*2].L = max(tree[node*2].L, tree[node].L);
        tree[node*2].R = max(tree[node*2].R, tree[node*2].L);
        tree[node*2].R = min(tree[node*2].R, tree[node].R);
        tree[node*2].L = min(tree[node*2].L, tree[node*2].R);
        tree[node*2+1].L = max(tree[node*2+1].L, tree[node].L);
        tree[node*2+1].R = max(tree[node*2+1].R, tree[node*2+1].L);
        tree[node*2+1].R = min(tree[node*2+1].R, tree[node].R);
        tree[node*2+1].L = min(tree[node*2+1].L, tree[node*2+1].R);
        upd(node*2,s,mid,l,r,diff,op); upd(node*2+1,mid+1,e,l,r,diff,op);
        tree[node].L = min(tree[node*2].L, tree[node*2+1].L);
        tree[node].R = max(tree[node*2].R, tree[node*2+1].R);
    }
    ll query(ll node, ll s, ll e, ll idx){
        if(idx<s or e<idx)return 0;
        if(s==e)return tree[node].L;
        tree[node*2].L = max(tree[node*2].L, tree[node].L);
        tree[node*2].R = max(tree[node*2].R, tree[node*2].L);
        tree[node*2].R = min(tree[node*2].R, tree[node].R);
        tree[node*2].L = min(tree[node*2].L, tree[node*2].R);
        tree[node*2+1].L = max(tree[node*2+1].L, tree[node].L);
        tree[node*2+1].R = max(tree[node*2+1].R, tree[node*2+1].L);
        tree[node*2+1].R = min(tree[node*2+1].R, tree[node].R);
        tree[node*2+1].L = min(tree[node*2+1].L, tree[node*2+1].R);
        ll mid = s+e>>1;
        return query(node*2,s,mid,idx)+query(node*2+1,mid+1,e,idx);
    }
} seg;
int main(){
    fast;
    cin>>n>>k;
    while(k--){
        ll a,b,c,d; cin>>a>>b>>c>>d;
        seg.upd(1,0,n-1,b,c,d,a);
    }
    for(int i = 0 ; i < n ; i++)cout<<seg.query(1,0,n-1,i)<<"\n";
}

위 코드는 아래 코드에서 쓸데없어보이는 거 한줄 지운건데 거의 2배가 느려졌다.