가로 블록 쌓기 (백준 18407)

안녕하세요. 오늘은 가로블록을 쌓을거예요.

문제

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

아이디어

길이가 w이고 시작점이 d이면 구간 [d,w+d]를 사용하게 됩니다.
그러면 각 점이 아닌 칸을 기준으로 본다면 d~d+1부터 w+d-1~w+d가 됩니다. 그래서 칸을 기준으로 구간 [d,w+d-1]을 차지하게 됩니다.

이 블록이 놓이는 높이는 어떻게 될까요? 바로 구간 [d,w+d-1]에서의 최댓값입니다. 그리고 갱신되는 높이는 그 최댓값 + 1이 됩니다. 정답은 전체에서의 최댓값이 되고요.

이를 빠르게 처리하는 자료구조가 있습니다. 바로 세그먼트 트리, 특히 느리게 갱신되는 세그먼트 트리입니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int tree[1010101] = { 0 }, lazy[1010101] = { 0 }; //최댓값 세그트리
void pp(int s, int e, int node)
{
    if (s != e)
    {
        lazy[node * 2] = max(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
    }
    tree[node] = max(tree[node], lazy[node]);
    lazy[node] = 0;
}
void change(int s, int e, int node, int l, int r, int num)
{
    pp(s, e, node);
    if (e < l || r < s) return;
    if (l <= s && e <= r)
    {
        lazy[node] = num;
        pp(s, e, node);
        return;
    }

    int mid = (s + e) / 2;
    change(s, mid, node * 2, l, r, num);
    change(mid + 1, e, node * 2 + 1, l, r, num);
    tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
int MAX(int s, int e, int node, int l, int r)
{
    pp(s, e, node);
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];

    int mid = (s + e) / 2;
    return max(MAX(s, mid, node * 2, l, r), MAX(mid + 1, e, node * 2 + 1, l, r));
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, i, a, b;
    vector <pair <int, int> > blocks;
    vector <int> num;

    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> a >> b;
        blocks.push_back({ b,a + b - 1 });
        num.push_back(b);
        num.push_back(a + b - 1);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());

    for (i = 0; i < N; i++)
    {
        blocks[i].first = lower_bound(num.begin(), num.end(), blocks[i].first) - num.begin() + 1;
        blocks[i].second = lower_bound(num.begin(), num.end(), blocks[i].second) - num.begin() + 1;

        int mx = MAX(1, 2 * N, 1, blocks[i].first, blocks[i].second);
        change(1, 2 * N, 1, blocks[i].first, blocks[i].second, mx + 1);
    }

    cout << MAX(1, 2 * N, 1, 1, 2 * N);
}

감사합니다.