백준3653 영화 수집

작성일 | In

문제 링크

  • http://icpc.me/3653

문제 출처

  • 2011 NWERC C번

사용 알고리즘

  • Segment Tree

시간복잡도

  • O((n+m) log (n+m))

풀이

영화가 n개가 있고, m개를 뽑아서 위로 올리는 문제입니다.
입력을 받을 때 m+1부터 m+n번 인덱스에 입력을 받고, 꺼내서 위로 올릴 때에는 앞에 빈 공간에 넣어주는 방식으로 문제를 해결할 것입니다.
해당 구간에 영화가 몇 개 있는지는 Segment Tree를 이용해 구하면 log 시간 안에 구할 수 있습니다.

구현이 까다로운 부분은 없으므로 자세한 설명은 생략하겠습니다.

전체 코드

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

vector<int> tree, arr;

void update(int node, int start, int end, int idx, int diff){
	if(idx<start || idx>end) return;
	tree[node] += diff;
	if(start^end){
		update(node*2, start, (start+end)/2, idx, diff);
     update(node*2+1, (start+end)/2+1, end, idx, diff);
	}
}

int sum(int node, int start, int end, int left, int right){
	if(left>end || right<start){
    	return 0;
	}
	if(left<=start && end<=right){
    	return tree[node];
	}
	return sum(node*2, start, (start+end)/2, left, right) + sum(node*2+1, (start+end)/2+1, end, left, right);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--){
		int n, m; cin >> n >> m;
		arr = vector<int>(n+m+10);
		tree = vector<int>(4*(n+m+10));

		for(int i=m+1; i<=n+m; i++){
			update(1, 1, n+m, i, 1);
			arr[i-m] = i;
		}
		int idx = m;

		for(int i=0; i<m; i++){
			int v; cin >> v;
			cout << sum(1, 1, n+m, 1, arr[v]-1) << " ";
			update(1, 1, n+m, arr[v], -1);
			arr[v] = idx--;
			update(1, 1, n+m, arr[v], 1);
		}
		cout << "\n";
	}
}