10070번: 벽 - 세그먼트 트리(lazy)

1.

구간을 갱신하는 문제이므로 무조건 lazy propagation을 써야 한다. 먼저 세그먼트 트리, lazy에 어떤 값을 넣어줄지 결정하자. 더하기 연산은 구간의 최솟값, 빼기 연산은 구간의 최댓값을 갱신하는 것과 다름없다. \(h\) 값에 따라 구간의 최댓값, 최솟값이 갱신되므로, 세그먼트 트리, lazy에 pair 형태로 {구간의 최솟값, 구간의 최댓값}을 저장해 주자.

 

2.

세그먼트 트리와 lazy에 값을 저장했다 가정하자. 그렇다면 쿼리가 들어올 때 높이를 어떻게 lazy해야 하는가? 위에서 더하기 연산은 구간의 최솟값, 빼기 연산은 구간의 최댓값을 갱신하는 것이라고 했다. 그렇다면 더하기 연산의 최댓값이 빼기 연산의 최솟값보다 크면 어떻게 될까?

 

예를 들어 높이 5로 빼는 연산을 진행한 후 높이 8로 더하는 연산을 진행한다 해보자. 이 경우, 이전 쿼리가 무엇이든 간에 해당 구간의 높이는 무조건 8이 될 수 밖에 없다. 높이 5로 뺀다는 것은 해당 구간의 높이의 최댓값이 5라는 것인데, 여기서 높이 8로 더하는 연산을 진행하면 모든 높이가 8이 되기 때문이다. 이 연산을 반대로 적용하여, 높이 8로 더하는 연산을 한 후 높이 5로 빼는 연산을 적용할 경우, 같은 원리로 해당 구간의 모든 높이는 5가 된다.

 

즉, ( 더하기 연산의 최댓값 > 빼기 연산의 최솟값) 이면 해당 구간의 높이가 동일해지므로, 해당 구간의 높이는 다음 쿼리에 들어오는 높이에 따라 결정된다.

이를 반대로 말하면,  구간의 (더하기 연산의 최댓값 < 빼기 연산의 최솟값) 일 때, 해당 구간의 최솟값, 최댓값은 { 더하기 연산의 최댓값, 빼기 연산의 최솟값}이다.

 

따라서 우리는 세그먼트 트리, lazy 값을 갱신할 때, 더하기 연산의 최댓값 < 빼기 연산의 최솟값 이라는 공식에 맞춰나갈 것이다. 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tll;

#define F first
#define S second
const int INF = 1e9;
const int MAXN = 2000001;
int n, k;
pii segTree[MAXN*4], lazy[MAXN*4];

void setLazy(int s, int e, int idx)
{
    auto [l, r] = lazy[idx];
    lazy[idx] = {-INF, INF};
    
    if(segTree[idx].S < l) segTree[idx] = {l, l}; //lazy의 최솟값보다 최댓값이 작으면 높이가 전부 l이 된다.
    else if(r < segTree[idx].F) segTree[idx] = {r, r}; //반대의 경우도 동일
    else segTree[idx] = {max(segTree[idx].F, l), min(segTree[idx].S, r)}; //세그트리와 lazy의 구간이 겹치는 구간이 곧 답
    
    //lazy 배열을 갱신할 때도 같은 방식으로 하면 된다.
    if(s != e)
    {
        if(lazy[idx*2].S < l) lazy[idx*2] = {l, l};
        else if(r < lazy[idx*2].F) lazy[idx*2] = {r, r};
        else lazy[idx*2] = {max(lazy[idx*2].F, l), min(lazy[idx*2].S, r)};
        
        if(lazy[idx*2+1].S < l) lazy[idx*2+1] = {l, l};
        else if(r < lazy[idx*2+1].F) lazy[idx*2+1] = {r, r};
        else lazy[idx*2+1] = {max(lazy[idx*2+1].F, l), min(lazy[idx*2+1].S, r)};
    }
}

void update(int s, int e, int l, int r, int idx, int h, int op)
{
    if(lazy[idx] != pii{-INF, INF}) setLazy(s, e, idx);
    
    if(e < l || r < s) return;
    if(l <= s && e <= r)
    {
        if(op == 1)
        {
            segTree[idx] = {max(segTree[idx].F, h), max(segTree[idx].S, h)};
            if(s != e)
            {
                lazy[idx*2] = {max(lazy[idx*2].F, h), max(lazy[idx*2].S, h)};
                lazy[idx*2+1] = {max(lazy[idx*2+1].F, h), max(lazy[idx*2+1].S, h)};
            }
        }
        else
        {
            segTree[idx] = {min(segTree[idx].F, h), min(segTree[idx].S, h)};
            if(s != e)
            {
                lazy[idx*2] = {min(lazy[idx*2].F, h), min(lazy[idx*2].S, h)};
                lazy[idx*2+1] = {min(lazy[idx*2+1].F, h), min(lazy[idx*2+1].S, h)};
            }
        }
        return;
    }
    
    update(s, (s+e)/2, l, r, idx*2, h, op);
    update((s+e)/2+1, e, l, r, idx*2+1, h, op);
    segTree[idx] = {min(segTree[idx*2].F, segTree[idx*2+1].F), max(segTree[idx*2].S, segTree[idx*2+1].S)};
}

int getVal(int s, int e, int m, int idx)
{
    if(lazy[idx] != pii{-INF, INF}) setLazy(s, e, idx);
    
    if(m < s || e < m) return 0;
    if(s == e) return segTree[idx].F;
    return getVal(s, (s+e)/2, m, idx*2) + getVal((s+e)/2+1, e, m, idx*2+1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

    cin >> n >> k;
    fill(lazy, lazy+MAXN*4, pii{-INF, INF}); //초깃값
    while(k--)
    {
        int op, l, r, h; cin >> op >> l >> r >> h;
        update(1, n, l+1, r+1, 1, h, op);
    }
    
    for(int i=1; i<=n; i++) cout << getVal(1, n, i, 1) << "\n";
}