[BOJ] 백준 8980 택배 (Segment Tree + Lazy Propagation)

　
Segment Tree + Lazy Propagation을 이용한 풀이입니다.
다른 풀이는 [BOJ] 8980 택배 참고

[BOJ] 백준 8980 택배

출처: https://www.acmicpc.net/problem/8980: 

 Input 

4 40

6

3 4 20

1 2 10

1 3 20

1 4 30

2 3 10

2 4 20

 

 Output 

70

도착지 기준으로 박스들을 정렬한 뒤, (도착지가 가까울 수록 최대한 많이 실을 수 있기 때문)

박스를 최대한 많이 실을려고 시도합니다.

이때, 실을려는 박스(box[i]) 배달 구간 [box[i].s, box[i].e)에서 최대한 실을 수 있는 남은 공간을 빠르게 구해야 합니다.

 

다시말해, 구간 최대값을 구하는 Segment Tree를 구현하고 단말 노드에는 해당 구간에 실린 양을 표시합니다.

그렇다면 특정구간 [s, e)에서 박스를 싣고자 할 때,

C - query(1, 1, N, box[i].s, box[i].e - 1);로 빠르게 확인할 수 있습니다. 

 

---

#include <stdio.h>
typedef long long LL;
inline int max(int a, int b) { return (a > b) ? a : b; }
const int MAX_N = 1e5;
const int MAX_C = 1e8;
const int MAX_M = 2e5;
const int treeSize = 1 << 18;
struct BOX {
    // 보내는 마을 번호, 받는 마을 번호, 박수개수
    int s, e, cost;
}box[MAX_M + 10], trr[MAX_M + 10];
// 마을 수, 트럭 용량, 박스 정보 수
int N, C, M;
int tree[treeSize]; // 구간 최대값
int lazy[treeSize]; // lazy propagation
 
void InitTree(int n, int s, int e) {
    lazy[n] = tree[n] = 0;
    if (s == e) return;
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    InitTree(L, s, m);
    InitTree(R, m + 1, e);
}
 
void LazyPropagation(int n, int s, int e) {
    if (lazy[n] == 0) return;
    tree[n] += lazy[n];// 구간 최대값
    if (s != e) {
        int L = n * 2, R = L + 1;
        lazy[L] += lazy[n];
        lazy[R] += lazy[n];
    }
    lazy[n] = 0;
}
 
int query(int n, int s, int e, int qs, int qe) {
    LazyPropagation(n, s, e);
    if ((qe < s) || (e < qs)) return 0;
    if ((qs <= s) && (e <= qe)) return tree[n];
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    // 구간 최대값
    return max(query(L, s, m, qs, qe), query(R, m + 1, e, qs, qe));
}
 
void update(int n, int s, int e, int qs, int qe, int val) {
    LazyPropagation(n, s, e);
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    if ((qe < s) || (e < qs)) return;
    if ((qs <= s) && (e <= qe)) {
        tree[n] += val;
        if (s != e) {
            lazy[L] += val;
            lazy[R] += val;
        }
        return;
    }
    update(L, s, m, qs, qe, val);
    update(R, m + 1, e, qs, qe, val);
    tree[n] = max(tree[L], tree[R]);
}
 
void mergeSort(int start, int end) {
    if (start >= end)
        return;
 
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
 
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (box[i].e <= box[j].e)
            trr[k++] = box[i++];
        else
            trr[k++] = box[j++];
    }
 
    while (i <= mid) trr[k++] = box[i++];
    while (j <= end) trr[k++] = box[j++];
    for (i = start; i <= end; i++)
        box[i] = trr[i];
}
 
void input() {
    scanf("%d %d", &N, &C);
    scanf("%d", &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d %d %d", &box[i].s, &box[i].e, &box[i].cost);
    }
}
 
LL solve() {
    LL sum = 0;
    // (받는 마을 기준) 오름차순 정렬
    mergeSort(1, M); 
    InitTree(1, 1, N);
    for (int i = 1; i <= M; i++) {
        // 해당 구간에서 배달할 수 있는 남은 용량
        int v = C - query(1, 1, N, box[i].s, box[i].e - 1);
 
        // 실을 수 있는 만큼만 싣기
        if (box[i].cost < v) v = box[i].cost;
        sum += v;
        // 해당 구간에 v가 실린 것을 표시
        update(1, 1, N, box[i].s, box[i].e - 1, v);
    }
    return sum;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%lld\n", solve());
}