백준 #10713 기차 여행

BOJ #10713 - 기차 여행

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

# 문제 분류

누적 합 OR 세그먼트 트리 with Lazy Propagation

풀이 접근 방법

날이 지날때마다 여러 도시를 경유하여 다닙니다.
만약 경유하는 도시를 모두 셀 경우에, 최악의 경우가 되는 경우에는 시간 초과가 일어날 수 있습니다.
따라서, 각 철도를 우리가 몇번 일어나는지만 빠르게 구한다면 문제를 해결할 수 있습니다.
여기서 두 가지 알고리즘이 등장합니다. 하나는 누적 합과 다른 하나는 lazy propagation을 이용한 세그먼트 트리입니다.
lazy를 사용하는 문제 같더라도 누적 합으로 해결할 수 있는 되게 재미있는 문제였습니다.

lazy 관련 문제라 들어갔는데 Silver여서 깜짝 놀란 기억이..

소스 코드

Prefix sum을 이용한 해답입니다.

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 1e5 + 10;
typedef long long ll;

int N, M, a[MAX], b[MAX], c[MAX], p[MAX];
int range[MAX];

int main() {
    cin >> N >> M;

    for (int i = 1; i <= M; i++) {
        cin >> p[i];
    }

    for (int i = 2; i <= M; i++) {
        int prev = p[i - 1];
        int next = p[i];

        if (prev > next)
            swap(prev, next);
        range[prev]++;
        range[next]--;
    }

    for (int i = 1; i < N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }

    ll result = 0, sum = 0;
    for (int i = 1; i < N; i++) {
        sum += range[i];
        result += min(sum * a[i], sum * b[i] + c[i]);
    }

    cout << result;
}

Segment tree with lazy propagation을 이용한 풀이입니다.

#include <algorithm>
#include <iostream>

using namespace std;

typedef long long ll;

const int MAX = 1 << 18;
int arr[MAX], lazy[MAX];
int N, M, p[(int)1e5 + 10];

int A[(int)1e5 + 10], B[(int)1e5 + 10], C[(int)1e5 + 10];

struct SegTree {
    int start = MAX / 2;

    SegTree() {
        fill(arr, arr + MAX, 0);
    }

    ll query(int node, int s, int e, int l, int r) {
        propagate(node, s, e);
        if (r < s || e < l)
            return 0;
        if (l <= s && e <= r)
            return arr[node];
        int m = s + e >> 1;
        return query(node << 1, s, m, l, r) + query(node << 1 | 1, m + 1, e, l, r);
    }

    void propagate(int node, int ns, int ne) {
        if (lazy[node]) {
            if (node < start) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }

            arr[node] += lazy[node] * (ne - ns + 1);
            lazy[node] = 0;
        }
    }

    void add(int s, int e, int k) { add(s, e, k, 1, 0, start - 1); }
    void add(int s, int e, int k, int node, int ns, int ne) {
        propagate(node, ns, ne);

        if (e < ns || ne < s)
            return;
        if (s <= ns && ne <= e) {
            lazy[node] += k;
            propagate(node, ns, ne);
            return;
        }

        int mid = (ns + ne) / 2;
        add(s, e, k, node * 2, ns, mid);
        add(s, e, k, node * 2 + 1, mid + 1, ne);
        arr[node] = arr[node * 2] + arr[node * 2 + 1];
    }
};

int main() {
    cin >> N >> M;

    SegTree st;

    for (int i = 1; i <= M; i++) {
        cin >> p[i];
    }

    for (int i = 2; i <= M; i++) {
        int prev = p[i - 1];
        int next = p[i];

        if (prev > next)
            swap(prev, next);

        st.add(prev - 1, next - 2, 1);
    }

    for (int i = 1; i < N; i++) {
        cin >> A[i] >> B[i] >> C[i];
    }

    ll r = 0;

    for (int i = 1; i < N; i++) {
        ll result = st.query(1, 0, st.start - 1, i - 1, i - 1);
        r += min(result * A[i], result * B[i] + C[i]);
    }

    cout << r;
}