백준10167 금광

작성일 | In

문제 링크

  • http://icpc.me/10167

문제 출처

  • 2014 KOI 전국 본선 중등부 4번

사용 알고리즘

  • 세그먼트 트리
  • 스위핑

시간복잡도

  • O(N2 log N)

풀이

KOI 초/중등부에 자주 나왔던(고기잡이, 금강석 등등) 아이디어를 하나 떠올려봅시다.
각 변에 모두 하나 이상의 금광이 걸쳐 있는 직사각형만 봐도 항상 정답을 찾을 수 있습니다.
그러므로 x, y좌표를 각각 압축해주면 x, y값이 각각 최대 6000개 존재하게 됩니다.

범위가 최대 6000이므로 O(N2 log N) 정도의 풀이를 생각해볼 수 있습니다.
직사각형의 가로 변을 정할 때 금광의 y좌표들 중에서 가능한 모든 (y1, y2)쌍을 선택해보면 O(N2)이 걸립니다. 만약 (y1, y2)가 고정되었을 때 최댓값을 O(log N)만에 구할 수 있다면 O(N2 log N)만에 문제를 풀 수 있습니다.

이제는 점점 웰노운이 되어가는, (l, r) 구간 안에서 연속 부분 최댓값을 저장하는 세그먼트 트리를 사용한다면 (y1, y2)가 고정되었을 때 최댓값을 O(log N)만에 구할 수 있습니다.

구현 방법을 다시 정리해보면

  1. 점들을 y좌표 기준으로 정렬
  2. y1을 고정하고 세그 트리 초기화
  3. y1부터 시작해서 y좌표를 점점 증가시켜가며 직사각형에 넣어주면서 세그 트리 갱신

y좌표가 같은 점은 동시에 직사각형에 넣어야 하는 것만 주의해주면 됩니다.

전체 코드

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;

struct p{
	ll x, y, w;
	bool operator < (const p &t) const {
		if(x != t.x) return x < t.x;
		return y < t.y;
	}
};

struct Node{
	ll sum, l, r, lr;
};

int bias = 4096;
Node tree[8282];

void init(){
	for(int i=0; i<8282; i++){
		tree[i].sum = tree[i].l = tree[i].r = tree[i].lr = 0;
	}
}

Node f(Node &a, Node &b){
	Node ret;
	ret.sum = a.sum + b.sum;
	ret.l = max(a.l, a.sum + b.l);
	ret.r = max(b.r, a.r + b.sum);
	ret.lr = max({a.r + b.l, a.lr, b.lr, ret.sum});
	return ret;
}

void update(int x, int v){
	x |= bias; tree[x].sum = tree[x].l = tree[x].r = tree[x].lr += v;
	while(x >>= 1){
		tree[x] = f(tree[x << 1], tree[x << 1 | 1]);
	}
}

Node query(int l, int r){
	l |= bias, r |= bias;
	Node ret = {0, 0, 0};
	while(l <= r){
		if(l & 1) ret = f(tree[l++], ret);
		if(~r & 1) ret = f(ret, tree[r--]);
		l >>= 1, r >>= 1;
	}
	return ret;
}

vector<p> v;
vector<ll> xx, yy;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n);
	for(auto &i : v){
		cin >> i.x >> i.y >> i.w;
		xx.push_back(i.x);
		yy.push_back(i.y);
	}
	sort(all(xx)); sort(all(yy));
	xx.erase(unique(all(xx)), xx.end());
	yy.erase(unique(all(yy)), yy.end());
	for(auto &i : v){
		i.x = lower_bound(all(xx), i.x) - xx.begin();
		i.y = lower_bound(all(yy), i.y) - yy.begin();
		swap(i.x, i.y);
	}
	sort(all(v));

	ll ret = 0;

	for(int i=0; i<n; i++){
		if(i && v[i-1].x == v[i].x) continue;
		init();
		for(int j=i; j<n; j++){
			update(v[j].y, v[j].w);
			if(j == n-1 || v[j].x != v[j+1].x) ret = max(ret, tree[1].lr);
		}
	}
	cout << ret;
}