LRH 식물 (백준 2934)

안녕하세요. 오늘은 식물을 키울거예요.

문제

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

아이디어

[L,R]에 식물이 생기면 L과 R에 있는 가로선의 개수를 0으로 만들고 그 개수를 출력해주면 됩니다.
또한 [L+1,R-1]에 있는 가로선의 개수에 모두 +1씩 해주면 됩니다.
이것을 느리게 갱신되는 세그먼트 트리로 해결해주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll tree[404040] = { 0 }, lazy[404040] = { 0 };
void pp(ll s, ll e, ll node)
{
    if (lazy[node])
    {
        tree[node] += lazy[node];
        if (s != e)
        {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
ll get_num(ll s, ll e, ll node, ll idx) //idx에 있는 값을 구하기
{
    pp(s, e, node);
    if (e < idx || idx < s) return 0;
    if (s == e) return tree[node];
    ll mid = (s + e) / 2;
    return get_num(s, mid, node * 2, idx) + get_num(mid + 1, e, node * 2 + 1, idx);
}
void change(ll s, ll e, ll node, ll l, ll r, ll num) //구간 [l,r]에 num씩 더하기
{
    pp(s, e, node);
    if (e < l || r < s) return;
    if (l <= s && e <= r)
    {
        lazy[node] = num;
        pp(s, e, node);
        return;
    }
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, l, r, num);
    change(mid + 1, e, node * 2 + 1, l, r, num);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, L, R;
    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> L >> R;
        ll left = get_num(1, 1e5, 1, L), right = get_num(1, 1e5, 1, R);
        cout << left + right << "\n";
        change(1, 1e5, 1, L, L, -left); //위치 L에 있는 값에서 left값만큼 빼기
        change(1, 1e5, 1, R, R, -right); //위치 R에 있는 값에서 right값만큼 빼기
        if (L + 1 < R) //사이에 빈 공간이 있다면
            change(1, 1e5, 1, L + 1, R - 1, 1);
    }
}

감사합니다.