BOJ 15506 : 정원사

• 문제 링크 : boj.kr/15506
• 난이도 : D4
• 태그 : 세그먼트 트리, 우선순위 큐

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

template<typename T>
class segTree {
private:
    ll n;
    T id;
    T(*merge)(T, T);
    vector<T> tree;
public:
    segTree(ll n, T id, T(*merge)(T, T)) {
        this->n = n;
        this->id = id;
        this->merge = merge;
        tree.resize(n*4, id);
    }
    void update(ll idx, T value) {
        _update(1, 1, n, idx, value);
    }
    T query(ll l, ll r) {
        return _query(1, 1, n, l, r);
    }
private:
    void _update(int node, int s, int e, int idx, T value) {
        if(idx < s || e < idx) return;

        if(s == e) {
            tree[node] = value;
            return;
        }

        _update(node*2, s, (s+e)/2, idx, value);
        _update(node*2+1, (s+e)/2+1, e, idx, value);
        tree[node] = merge(tree[node*2], tree[node*2+1]);
    }
    T _query(int node, int s, int e, int l, int r) {
        if(l > e || r < s) return id;
        if(l <= s && e <= r) return tree[node];

        T lq = _query(node*2, s, (s+e)/2, l, r);
        T rq = _query(node*2+1, (s+e)/2+1, e, l, r);
        return merge(lq, rq);
    }
};

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

    ll n, m, k;
    cin >> n >> m >> k;
    vector<priority_queue<ll>> garden(n+1);
    segTree<pll> seg_max(n, pll(-1e18, -1), [](pll a, pll b){return max(a,b);});
    for(int i = 1; i <= n; i++) {
        garden[i].push(-1e18);
        seg_max.update(i, {garden[i].top(), i});
    }
    segTree<ll> seg_sum(n, 0, [](ll a, ll b){return a+b;});
    for(int i = 0; i < m; i++) {
        ll q, a, b, c, d;
        cin >> q;
        if(q == 1) {
            cin >> a >> b >> c;
            garden[b].push(c-a*k);
            seg_max.update(b, {garden[b].top(), b});
            seg_sum.update(b, garden[b].size()-1);
        }
        if(q == 2) {
            cin >> a >> b >> c >> d;
            ll pivot = d-a*k;
            while(true) {
                pll curr = seg_max.query(b, c);
                if(curr.first <= pivot) break;
                ll idx = curr.second;
                garden[idx].pop();
                seg_max.update(idx, {garden[idx].top(), idx});
                seg_sum.update(idx, garden[idx].size()-1);
            }
        }
        if(q == 3) {
            cin >> a >> b >> c;
            cout << seg_sum.query(b, c) << "\n";
        }
    }


    return 0;
}

---

풀이

우선 각 정원에 최대 한 개의 식물만 심을 수 있다고 해보자.

식물이 자라는 속도는 동일하므로 특정 시점에 식물의 키가 몇인지 알면 뽑아야 할 식물을 쉽게 알 수 있다.

#20772에서 사용했던 테크닉을 이용하면 0일차를 기준으로 식물의 키를 설정할 수 있게 된다.

식물을 심는 것이 최대 M번이므로, 식물을 뽑아야 할 때 매번 조건을 확인해서 한 개씩 뽑아도 시간 복잡도에는 문제가 없다.

이는 세그먼트 트리로 쉽게 구현할 수 있다.

 

이제 정원에 식물을 여러 개 심을 수 있다고 해보자.

앞에서 식물을 한 개씩 뽑아도 문제가 없다는 사실을 알았으므로 한 정원에서는 최대 한 개의 식물만 확인해도 된다는 것을 알 수 있다.

따라서 각 정원이 가지고 있는 식물 중 가장 키가 큰 식물만 가지고 판단할 수 있다.

가장 큰 키, 그 다음 큰 키, 그 다음 큰 키 ... 를 구하기 위해 우선순위 큐를 사용할 수 있다.

 

단, 세그먼트 트리의 각 배열에 우선순위 큐를 사용하면 merge 과정에서 시간초과가 발생할 수 있다.

세그먼트 트리에는 정원의 대표값(최대값)과 인덱스만 저장하고, 필요한 경우에 정원에 직접 접근해서 우선순위 큐를 다뤄주면 O(MlogM)으로 해결할 수 있다.