백준10713 기차 여행

작성일 | In

문제 링크

  • http://icpc.me/10713

문제 출처

  • 2015 JOI 1번

사용 알고리즘

  • Segment Tree
  • Lazy Propagation

시간복잡도

  • O(n log n)

풀이

i번과 i+1번 도시를 잇는 철도를 i번 철도라고 부릅시다.

기본적인 아이디어는 i번 철도를 지나는 횟수를 k라고 했을 때, a[i] * k와 b[i] * k + c[i] 중 더 작은 값이 해당 철도의 총 이용료가 된다는 것입니다.
그러면 이동할 구간이 주어졌을 때, 해당 구간 안에 있는 모든 철도의 이용 횟수를 빠르게 업데이트할 방법만 찾으면 됩니다.
Segment Tree에서 Lazy Propagation을 사용하면 효율적으로 할 수 있습니다.

전체 코드

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
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct lazySeg{
	ll tree[401010];
	ll lazy[401010];

	void lzy(int node, int s, int e){
		if(!lazy[node]) return;
		tree[node] += (e-s+1) * lazy[node];
		if(s ^ e){
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
		}
		lazy[node] = 0;
	}

	void update(int node, int s, int e, int l, int r){
		lzy(node, s, e);
		if(r < s || e < l) return;
		if(l <= s && e <= r){
			tree[node] += (e-s+1);
			if(s ^ e){
				lazy[node<<1]++;
				lazy[node<<1|1]++;
			}
			return;
		}
		int m = s + e >> 1;
		update(node<<1, s, m, l, r);
		update(node<<1|1, m+1, e, l, r);
		tree[node] = tree[node<<1] + tree[node<<1|1];
	}

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

int a[101010], b[101010], c[101010]; //use ticket, use card, buy card
int path[101010];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	for(int i=0; i<m; i++){
		cin >> path[i];
	}

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

	for(int i=1; i<m; i++){
		int s = min(path[i-1], path[i]);
		int e= max(path[i-1], path[i])-1;
		cnt.update(1, 1, n-1, s, e);
	}

	ll ans = 0;
	for(int i=1; i<n; i++){
		ll t = cnt.query(1, 1, n-1, i, i);
		ans += min(a[i]*t, b[i]*t + c[i]);
	}
	cout << ans;
}