BOJ 10167 - 금광 (세그트리, 분할정복)

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

현장에서 100%받은 학생이 없었다는 문제

 

https://www.youtube.com/watch?v=NHf7v-_azYs&list=PLN3yisVKGPfh_sdb_pxGMP3lTF91DOgOr&index=31

위 영상 참고했습니다.

 

www.acmicpc.net/problem/17975

유사문제

 

 

<문제설명>

좌표평면 위에 최대 3000개의 정점이 주어진다. 각 정점마다 cost가 주어진다.

 

어떤 직사각형 안에 담을 수 있는 cost합의 최대를 구하라

 

 

<접근 및 풀이>

1.

좌표압축을 해도 문제의 통일성을 해치지 않는다. 좌표값을 10의 9승에서 10의 3승정도로 줄일 수 있다.

 

2.

직사각형의 좌하단 꼭지점을 (x1,y1), 우상단 꼭지점을 (x2,y2)라고 뒀을 때 최대값이 바로 정해지므로, x1,y1,x2,y2를 하나씩 골라주는 방식으로 짠다면 O(n^4)이 된다. ->너무 느리다.

 

3.

y1과 y2가 정해졌을 때 구간 최대값은 분할정복을 이용해서 구할 수 있다.

(1차원 구간합의 최대값을 분할정복으로 구하는 방법을 떠올리면 쉽게 생각할 수 있다. (물론 1차원구간합의 최대값은 더 쉽게 구할 수 있다.))

 

점화식

y2를 y1부터 ymx까지 올리면서 생각해보면, 세그트리를 업데이트하면서 문제를 풀 수 있다는 것을 알 수 있다.

 

 

 

4.

seg[i] : x의 구간 i에 대해 {총합, 왼쪽절반 최대값, 오른쪽절반 최대값, 최대값}을 담아서 새로운 (x,cost)를 모두 업데이트한 후 정답을 갱신해주면 된다.

 

 

<코드>

typedef pair<int, int> P;
typedef tuple<ll, ll, ll, ll> T;
const int MAX = 3e3 + 4;
const int SMAX = (1 << 13);

int n,ymx;
vector<int> xp, yp;
tuple<int, int, int> inp[MAX];
vector<P> g[MAX];

T seg[SMAX];
T oper(T t1, T t2) {
	ll sum, lsum, rsum, mx;
	ll left_sum, left_lsum, left_rsum, left_mx;
	ll right_sum, right_lsum, right_rsum, right_mx;
	tie(left_sum, left_lsum, left_rsum, left_mx) = t1;
	tie(right_sum, right_lsum, right_rsum, right_mx) = t2;

	sum = left_sum + right_sum;
	lsum = max(left_lsum, left_sum+ right_lsum);
	rsum = max(right_rsum, right_sum + left_rsum);
	mx = max({ left_mx, right_mx, left_rsum + right_lsum });
	return { sum, lsum, rsum, mx };
}

void update(int i, int c) {
	i += SMAX / 2;
	get<0>(seg[i]) += c;
	get<1>(seg[i]) += c;
	get<2>(seg[i]) += c;
	get<3>(seg[i]) += c;
	while (i > 1) {
		i /= 2;
		seg[i] = oper(seg[i * 2], seg[i * 2 + 1]);
	}
}

int main() {
	FAST; cin >> n;
	for (int i = 0,x,y,w; i < n; i++) {
		cin >> x >> y >> w;
		inp[i] = { x,y,w };
		xp.push_back(x);
		yp.push_back(y);
	}
	sort(xp.begin(), xp.end());
	sort(yp.begin(), yp.end());
	xp.erase(unique(xp.begin(), xp.end()), xp.end());
	yp.erase(unique(yp.begin(), yp.end()), yp.end());

	for (int i = 0,x,y,w; i < n; i++) {
		tie(x, y, w) = inp[i];
		x = lower_bound(xp.begin(), xp.end(), x) - xp.begin();
		y = lower_bound(yp.begin(), yp.end(), y) - yp.begin();
		g[y].push_back({ x,w });
		inp[i] = { x,y,w };
		ymx = max(y, ymx);
	}

	ll ans = 0;
	for (int y1 = 0; y1 <= ymx; y1++) {
		fill(seg, seg + SMAX, make_tuple(0, 0, 0, 0));
		for (int y2 = y1,x,c; y2 <= ymx; y2++) {
			for (P p : g[y2]) {
				tie(x, c) = p;
				update(x, c);
			}
			ans = max(ans, get<3>(seg[1]));
		}
	}
	cout << ans << '\n';
}