백준2957 이진 탐색 트리

작성일 | In

문제 링크

  • http://icpc.me/2957

문제 출처

  • 2008/2009 COCI Contest #3 5번

사용 알고리즘

  • Union-Find

시간복잡도

  • O(NlogN)
  • O(N)

풀이

set을 사용한 O(NlogN)풀이와 Union Find를 사용한 O(N)풀이가 있습니다.

x를 삽입할 때 트리에 있는 원소 중 x보다 작은 최댓값, x보다 큰 최솟값을 찾으면 아래 두 가지 형태 중 하나가 나옵니다.

두 정점을 a, b라고 하면 dep[x] = max(dep[a], dep[b]) + 1이 됩니다.

set을 써서 계산을 해주면 O(NlogN)이 나옵니다.

처음에는 모든 공간이 비어있는 상태이고, 원소가 삽입될 때 마다 연속된 빈 공간이 둘로 쪼개진다고 생각할 수 있습니다.
연속된 빈 공간을 하나의 노드로 보고, 바로 왼쪽과 오른쪽의 있는 숫자를 관리해주는 union find를 생각해볼 수 있습니다.
집합을 쪼개는 것은 어렵지만, 거꾸로 생각하면 모두 쪼개진 상태에서 하나씩 union하는 것은 가능하기 때문에 거꾸로 처리를 해주면 됩니ㅠ다. (ex. KOI2016 중등 3번 트리)

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int par[303030];
int l[303030];
int r[303030];
int lf[303030];
int rf[303030];
ll dep[303030];
vector<int> v;
int n;

int find(int v){
	return v == par[v] ? v : par[v] = find(par[v]);
}

void merge(int u, int v){
	if(u < 1 || v < 1 || u > n || v > n) return;
	u = find(u), v = find(v);
	par[u] = v;
	l[v] = min(l[v], l[u]);
	r[v] = max(r[v], r[u]);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n+1);
	for(int i=1; i<=n; i++) cin >> v[i];

	for(int i=n; i>=1; i--){
		par[v[i]] = v[i]; l[v[i]] = v[i] - 1; r[v[i]] = v[i] + 1;
		int j = find(v[i]);
		if(find(l[j])) merge(l[j], j);
		if(find(r[j])) merge(r[j], j);
		j = find(j);
		lf[i] = l[j], rf[i] = r[j];
	}
	ll ans = 0;
	cout << 0 << "\n";
	for(int i=2; i<=n; i++){
		dep[v[i]] = max(dep[lf[i]], dep[rf[i]]) + 1;
		ans += dep[v[i]];
		cout << ans << "\n";
	}
}