백준 8987 수족관 3 (KOI 2013 4번)

문제 설명(링크)

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

8987번: 수족관 3

풀이

풀이가 다양한 것 같은데, 내가 푼 풀이 기준으로 설명하겠다. 

 

우선 수족관의 모양이 히스토그램과 유사하므로, 카르테시안 트리로 모델링할 수 있다. 수족관을 카르테시안 트리로 모델링하면 특정 정점을 선택하면 그 정점과 그 정점의 모든 조상 정점에 해당하는 영역의 물이 빠진다. 또한 한번 물이 빠진 영역은 당연하게도 물을 다시 뺄 수 없다.

 

이런 특성들을 생각하면, 여러가지 정리들을 관찰 할 수 있다.

 

1. 카르테시안 트리의 리프에 해당하는 부분에만 구멍을 낸다 생각해도 상관없다.

만약 리프에 해당하는 부분에 구멍을 내지 않았다면 그 영역의 자손에 구멍을 낼 경우 더 많은 물을 뺄 수 있기 때문이다.

 

2. 1에 의해 물을 빼기 위해 리프 노드들을 선택할 때, 초기 상태에서 하나의 리프 노드만 선택한다고 할 때 가장 많은 물을 뺄 수 있는 정점은 반드시 선택된다.

만약 모든 정점들을 선택할 때까지 초기 상태에서 최대한 많은 물을 뺄 수 있는 곳의 물을 빼지 않았다면, 그 정점과 lca의 깊이가 가장 깊은 정점의 선택을 취소하고, 이 정점을 선택하는게 이득이기 때문이다.

 

이제 이 두 관찰로부터 풀이를 생각할 수 있다. 우선 가장 많은 물을 뺄 수 있는 리프 노드를 선택한 뒤, 리프 노드와 그 노드의 모든 조상에 해당하는 물을 모두 빼 준다. 그리고 이를 K번 반복하면 된다. 설명은 쉬운데, 이는 구현이 약간 어렵다. 일단 오일러 투어의 아이디어를 적용하면, 하나의 노드에 해당하는 물이 모두 빠질 때, 그 노드의 자손 노드들에 대해 각 노드를 제거했을 때 뺄수 있는 물의 양이 감소하게 되고, 물이 빠진 노드가 영향을 주는 리프 노드는 연속한다. 따라서 dfs순으로 리프를 잘 정렬해 주고, 각 리프에 대해 리프에 해당하는 영역에 구멍을 냈을 때 빠지는 물의 양을 Lazy Propagation을 지원하는 세그먼트 트리로 관리해 주고, 물을 가장 많이 뺄 수 있는 리프를 선택하고 리프의 부모에 물을 빼는 것을 K번 반복하면 된다. 이때 물을 뺄때는 리프에서 부모 방향으로 올라가면서 뺄 물이 없는 시점에 멈춰 주어야 한다. 이렇게 하면 각 정점에서 업데이트는 한 번 일어나고, 업데이트 횟수가 물이 이미 빠졌는지 확인하는 횟수와 최대 1 차이나므로 시간 복잡도가 총 $O(N)$번 확인하게 된다.

 

소스코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
struct segtree {
	ll N, s;
	vector<pll> tree;
	vector<ll> l, r, lazy;
	bool type = 1;
	void init(ll x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			tree[x].second = l[x];
			if (type && l[x] > N) tree[x].first = INF;
			if (!type && l[x] > N) tree[x].first = -INF;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		if (type) tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
	}
	segtree() {}
	segtree(ll _N, bool t = true) {
		type = t;
		N = _N;
		s = 1LL << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		if (!type) lazy.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
	}
	pll query(ll low, ll high, ll loc = 1) {
		if (low == l[loc] && high == r[loc]) return tree[loc];
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		if (type) return min(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
		else return min(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
	}
	void prop(ll loc) {
		if (loc >= s) return;
		tree[loc * 2].first += lazy[loc];
		tree[loc * 2 + 1].first += lazy[loc];
		lazy[loc * 2] += lazy[loc];
		lazy[loc * 2 + 1] += lazy[loc];
		lazy[loc] = 0;
	}
	void update(ll low, ll high, ll a, ll loc = 1) {
		if (!a) return;
		prop(loc);
		if (low == l[loc] && high == r[loc]) {
			lazy[loc] += a;
			tree[loc].first += a;
			return;
		}
		if (high <= r[loc * 2]) update(low, high, a, loc * 2);
		else if (low >= l[loc * 2 + 1]) update(low, high, a, loc * 2 + 1);
		else update(low, r[loc * 2], a, loc * 2), update(l[loc * 2 + 1], high, a, loc * 2 + 1);
		prop(loc);
		tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
	}
	void update(pll r, ll a) { update(r.first, r.second, a); }
	pll get() { return tree[1]; }
};
segtree seg;
vector<pair<ll, ll>> arr;
ll loc[MAX];
ll prt[MAX];
ll child[2][MAX];
ll ord[MAX];
ll val[MAX];
bool isleaf[MAX];
pll range[MAX];
ll rev[MAX];
ll vis[MAX];
ll make_tree(ll low, ll high, ll p = 0) {
	if (low > high) return 0;
	ll mid = seg.query(low, high).second;
	prt[mid] = p;
	val[mid] = (loc[high] - loc[low - 1]) * (arr[mid].second - arr[p].second);
	child[0][mid] = make_tree(low, mid - 1, mid);
	child[1][mid] = make_tree(mid + 1, high, mid);
	return mid;
}
ll cnt;
pll make_ord(ll x) {
	if (isleaf[x]) {
		ord[x] = ++cnt;
		rev[ord[x]] = x;
		return range[x] = { ord[x], ord[x] };
	}
	else {
		pll ret;
		if (child[0][x] && child[1][x]) ret.first = make_ord(child[0][x]).first, ret.second = make_ord(child[1][x]).second;
		else if (child[0][x]) ret = make_ord(child[0][x]);
		else if (child[1][x]) ret = make_ord(child[1][x]);
		return range[x] = ret;
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N;
	cin >> N;
	ll i;
	ll a, b, c, d;
	cin >> a >> b;
	N -= 2;
	arr.push_back({ 0, 0 });
	for (i = 1; i <= N / 2; i++) {
		cin >> a >> b >> c >> d;
		arr.push_back({ c - a, d });
		loc[++cnt] = c;
	}
	cin >> a >> b;
	N = cnt;
	seg = segtree(N);
	for (i = 1; i <= N; i++) seg.tree[seg.s + i - 1] = { arr[i].second, i };
	seg.init();
	ll r = make_tree(1, N);
	for (i = 1; i <= N; i++) if (!(child[0][i] + child[1][i])) isleaf[i] = true;
	cnt = 0;
	make_ord(r);
	segtree lazy = segtree(cnt, false);
	ll K;
	cin >> K;
	K = min(K, cnt);
	lazy.init();
	for (i = 1; i <= N; i++) lazy.update(range[i], val[i]);
	ll ans = 0;
	for (i = 1; i <= K; i++) {
		pll res = lazy.get();
		ans += res.first;
		ll v = res.second;
		v = rev[v];
		while (v) {
			if (vis[v]) break;
			vis[v] = 1;
			lazy.update(range[v], -val[v]);
			val[v] = 0;
			v = prt[v];
		}
	}
	cout << ans << ln;
}

총평

구현이 약간 오래 걸렸다.

여담으로, JOISC에 나온

Constellation 3

문제와 비슷하다.