백준2517 달리기

작성일 | In

문제 링크

  • http://icpc.me/2517

문제 출처

  • 2012 전국 본선 고등부2

사용 알고리즘

  • Segment Tree (혹은 Fenwick Tree)

시간복잡도

  • O(n log n)

풀이

수열과 쿼리1 문제(링크)의 offline query 방식과 유사한 아이디어로 해결할 수 있습니다.

자신보다 앞에 있는 사람 중, 평소 실력이 더 낮은 사람들은 이길 수 있는 사람들입니다. 자신보다 앞에 있는 사람들 중에서 자신보다 평소 실력이 더 낮은 사람의 수를 구하기만 하면 이 문제를 해결할 수 있습니다.

자신보다 앞에 있으면서, 실력이 더 낮은 사람들의 수를 구하는 방법을 알아봅시다.
i번째 사람의 평소 실력 t를 입력받으면 {i, t} 형태의 pair로 저장을 한 뒤, t를 기준으로 잡아 오름차순으로 정렬해줍시다.
t가 작은 것부터 아래 절차에 따라 쿼리를 날리고 답을 구합니다.

  1. query(1, idx-1) 형태로 세그먼트 트리에 쿼리를 날립니다. 이때 나온 결과가 자신보다 앞에 있으면서 실력이 낮은 사람의 수입니다.
  2. update(idx, 1) 형태로 세그먼트 트리에 쿼리를 날립니다.

update 쿼리를 통해 idx인덱스의 값을 1로 바꿔줌으로써 나중에 처리가 되는 사람들, 즉 t가 더 큰 사람들을 처리할 때 해당 위치에 실력이 낮은 사람이 있다는 것을 알 수 있습니다. 자세한 설명과 구현은 코드로 대체합니다.

전체 코드

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

struct Seg{
	int arr[2020202];
	int bias;

	void init(int n){
		memset(arr, 0, sizeof arr);
		for(bias = 1; bias < n; bias <<= 1);
	}

	void update(int x, int v){
		x |= bias;
		arr[x] = v;
		while(x >>= 1){
			arr[x] = arr[x<<1] + arr[x<<1|1];
		}
	}

	int query(int l, int r){
		l |= bias, r |= bias;
		int lval = 0, rval = 0;
		while(l <= r){
			if(l&1) lval = lval + arr[l++];
			if(!(r&1)) rval = rval + arr[r--];
			l >>= 1, r >>= 1;
		}
		return lval + rval;
	}
} tree;

typedef pair<int, int> p;
vector<p> v;

int ans[505050];


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n); tree.init(n);
	for(int i=0; i<n; i++){
		int t; cin >> t;
		v[i] = {i+1, t};
	}
	sort(v.begin(), v.end(), [&](p &a, p &b){
		return a.second < b.second;
	});

	for(auto &i : v){
		int idx = i.first;
		ans[idx] = idx - tree.query(1, idx-1);
		tree.update(idx, 1);
	}

	for(int i=1; i<=n; i++) cout << ans[i] << "\n";
}