[백준 15506] 정원사

작성일 | In |

문제 링크

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

풀이

우선 정원 하나마다 식물이 최대 한개씩만 들어온다고 생각하고 풀이를 생각해봅시다.

하루에 자라는 높이를 어떻게 처리할 수 있을까요? 추가했던 식물이 자라는 것이 아니라 나중에 추가될 식물의 높이를 줄인다고 생각해 봅시다. 1번 쿼리든 2번 쿼리든 높이를 $h - k ⋅ t$로 관리한다면 이전에 추가했던 식물의 높이를 수정할 필요 없이 같은 효과를 볼 수 있습니다.

만약 1번 쿼리로만 입력이 들어온다고 하더라도 최대 $M$개의 식물만을 심을 수 있습니다. 즉, 높이가 $h$를 초과한 식물을 하나씩 뽑아내는 방식으로 2번 쿼리를 처리해도 최대 $M$번의 연산으로 처리할 수 있습니다. [max, index]를 원소로 갖는 세그먼트 트리를 이용해$[l, r]$구간에 $h$를 초과한 식물이 있을 때까지 그 식물을 뽑아내면 구간에서 max 값을 찾는 데에 $O(\log N)$이고 2번 쿼리가 아무리 많이 들어온다 해도 뽑을 식물의 개수는 최대 $M$개 이므로 총 시간복잡도는 $O(M \log N)$입니다. 2번 쿼리를 처리하기 위해 세그먼트 트리를 떠올렸다면 3번 쿼리 또한 sum 값을 원소로 갖는 세그먼트 트리를 이용해 $[l, r]$구간의 합을 구할 수 있다는 것을 알아낼 수 있습니다. 3번 쿼리의 시간복잡도는 $O(\log N)$입니다.

여러개의 식물을 관리하기 위해서는 어떻게 해야 할까요?

우리가 정원에서 세그먼트 트리를 하는 데에 필요한 정보는 정원에서의 식물 중 최대 높이 (2번 쿼리)와 정원에 있는 식물의 개수 (3번 쿼리) 입니다. 이 두 값을 효율적으로 관리하기 위해 정원을 뜯하는 세그먼트 트리의 리프노드마다 식물을 우선순위 큐로 관리한다면 식물 중 최대 높이와 정원에 있는 식물의 개수를 알아낼 수 있습니다. 이 방식으로는 식물 추가 횟수 최대 $M$번, 최대 높이의 식물 제거 횟수 최대 $M$번으로 우선순위 큐에서 사용하는 총 시간복잡도는 $O(M \log M)$ 입니다.

문제를 푸는 데에 사용한 가장 큰 시간복잡도는 $O(M \log M)$으로 시간 내에 들어올 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l + r) >> 1)

int n, m, t2[400400];
ll k, INF = 1e18;
pair<ll, int> t[400400];
priority_queue<ll> pq[100100];

void update(int id, ll val, int node = 1, int l = 1, int r = n){
    if(id < l || r < id) return;
    if(l == r){
        if(val == INF) pq[l].pop();
        else pq[l].push(val);
        t[node] = {pq[l].empty() ? -INF : pq[l].top(), l};
        t2[node] = pq[l].size();
        return;
    }
    update(id, val, node*2, l, mid), update(id, val, node*2+1, mid+1, r);
    t[node] = max(t[node*2], t[node*2+1]);
    t2[node] = t2[node*2] + t2[node*2+1];
}

pair<ll, int> find_max(int nl, int nr, int node = 1, int l = 1, int r = n){
    if(r < nl || nr < l) return {-INF, 0};
    if(nl <= l && r <= nr) return t[node];
    return max(find_max(nl, nr, node*2, l, mid), find_max(nl, nr, node*2+1, mid+1, r));
}

int find_sum(int nl, int nr, int node = 1, int l = 1, int r = n){
    if(r < nl || nr < l) return 0;
    if(nl <= l && r <= nr) return t2[node];
    return find_sum(nl, nr, node*2, l, mid) + find_sum(nl, nr, node*2+1, mid+1, r);
}

int main(){
    scanf("%d %d %lld",&n,&m,&k);
    for(int i=1;i<=4*n;i++) t[i] = {-1e18, 0};
    while(m--){
        int a, t; scanf("%d %d",&a,&t);
        if(a == 1){
            int x, h; scanf("%d %d",&x,&h);
            update(x, h - k * t);
        }else if(a == 2){
            int l, r, h; scanf("%d %d %d",&l,&r,&h);
            while(1){
                auto [x, y] = find_max(l, r);
                if(x <= h - k * t) break;
                update(y, INF);
            }
        }else if(a == 3){
            int l, r; scanf("%d %d",&l,&r);
            printf("%d\n",find_sum(l, r));
        }
    }
}