백준 BOJ 2934번 : LRH 식물 (느리게 갱신되는 세그먼트 트리)

백준 BOJ 2934번 : LRH 식물

문제 난이도 : Platinum IV

알고리즘 분류 : 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree)

 

 

 

매일 높이가 1씩 높아지는 선분들을 위와 같이 그린다고 할 때, 매일 발생하는 새로운 교차점의 수를 구하는 문제입니다.

이 때 중요한 점은 두 선분이 완전히 교차하지 않거나 이미 교차가 발생했던 지점은 교차점으로 세지 않는다는 것입니다.

 

상황을 바꾸어 생각해보면, 매 쿼리마다 L ~ R 구간에 높이가 1인 블럭들을 쌓고, 이 때 L 지점과 R 지점의 높이를 구하면 어느 정도 비슷하게 해결이 될 것 같습니다.

 

 

 

그런데 문제는 위에서 말한 두 선분이 완전히 교차하지 않는 지점과 교차가 발생했던 지점의 처리입니다.

먼저 두 선분이 완전히 교차하지 않는다는 것은 1번의 경우를 말하고, 이미 교차하여 Count 된 경우는 2번의 경우를 말합니다.

 

양 끝 지점의 특징에 대해 잘 생각해보면 양 끝 점이 한 번 찍은 지점에서는 새로운 교차가 발생할 수 없습니다.

따라서 두 가지를 한 번에 해결할 수 있는 아이디어는, 양 끝 점의 좌표에 쌓여있는 값들을 Count 먼저 해주고, 그 다음 양 끝 점의 값을 다시 0으로 초기화하는 것입니다.

 

L ~ R 구간에 값을 1씩 더하여 누적시키는 것은 느리게 갱신되는 세그먼트 트리로 구현이 가능하며, 특정 위치의 값을 불러오는 것 역시 log 시간에 가능하므로 O(N log 100000) 시간에 해결할 수 있습니다. (10만은 구간의 최대 길이)

 

 

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

vector<int> u, w; // u : tree, w : lazy

void lazy(int n, int b, int e) {
    if(w[n] == 0) return;

    u[n] += (e-b+1)*w[n];

    if(b != e) {
        w[n*2] += w[n];
        w[n*2 + 1] += w[n];
    }

    w[n] = 0;
}

int f(int n, int b, int e, int idx) {
    lazy(n, b, e);

    if(b == e) return u[n];

    if(idx <= (b+e)/2) return f(n*2, b, (b+e)/2, idx);
    else return f(n*2 + 1, (b+e)/2 + 1, e, idx);
}

int g(int n, int b, int  e, int l, int r, int add) {
    lazy(n, b, e);

    if(r < b || e < l) return u[n];

    if(l <= b && e <= r) {
        w[n] += add;
        lazy(n, b, e);
        return u[n];
    }

    int lv = g(n*2, b, (b+e)/2, l, r, add);
    int rv = g(n*2 + 1, (b+e)/2 + 1, e, l, r, add);

    return u[n] = lv + rv;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    int MAX = 100000;

    u.resize(MAX*4);
    w.resize(MAX*4);

    int ans = 0;
    while(N--) {
        int l, r; cin >> l >> r;

        cout << f(1, 1, MAX, l) + f(1, 1, MAX, r) << "\n";

        g(1, 1, MAX, l, r, 1);

        g(1, 1, MAX, l, l, -f(1, 1, MAX, l));
        g(1, 1, MAX, r, r, -f(1, 1, MAX, r));
    }
}

 

f 함수의 경우 f(x)를 하면 x 좌표의 값을 받아오는 기능을 수행하고, g 함수의 경우 L ~ R 구간 전체에 1씩 값을 누적시켜주는 연산을 log 시간에 수행해줍니다.