[ BOJ ] 1849 : 순열 ( PLATINUM 5 ) / C

문제

1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라. 

입력

첫째 줄에 수열 원소의 개수 (1 ≤ N ≤100,000)이 주어진다. 그리고 두 번째 줄부터 N+1 번째 줄까지 차례로 A[i]가 주어진다.

출력

N개의 줄에 걸쳐서 수열을 출력한다. (i번째 줄에는 i번째 원소를 의미한다)

풀이 과정

1부터 시작해서, 1보다 큰 수들이 앞에 최소한 A[1] 개 있다, 2보다 큰 수들이 앞에 최소한 A[2] 개 있다, 이런 식으로 수열을 작은 수부터 차례대로 배치한다. 모든 노드를 1로 설정하고 수를 배치했으면 0으로 바꿔 몇 번째에 수를 배치해야 하는지를 이분 탐색했다.

#include <stdio.h>
#define SIZE 100001

int arr[SIZE];
int result_arr[SIZE];
int zero_tree[SIZE * 4];

void init(int start, int end, int idx) {
	if (start == end) {
		zero_tree[idx] = 1;
		return;
	}

	int mid = (start + end) / 2;
	init(start, mid, idx * 2);
	init(mid + 1, end, idx * 2 + 1);
	zero_tree[idx] = zero_tree[idx * 2] + zero_tree[idx * 2 + 1];
}


int query(int start, int end, int idx, int key) {
	if (start == end) return start;
	if (zero_tree[idx * 2] >= key) return query(start, (start + end) / 2, idx * 2, key);
	else return query((start + end) / 2 + 1, end, idx * 2 + 1, key - zero_tree[idx * 2]);
}

void update(int start, int end, int idx, int what) {
	if (what < start || end < what) return;
	if (start == end) {
		zero_tree[idx] -= 1;
		return;
	}

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what);
	update(mid + 1, end, idx * 2 + 1, what);
	zero_tree[idx] = zero_tree[idx * 2] + zero_tree[idx * 2 + 1];
}

int main(void) {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

	init(0, n - 1, 1);

	for (int i = 0; i < n; i++) {
		int result = query(0, n - 1, 1, arr[i] + 1);
		update(0, n - 1, 1, result);
		result_arr[result] = i + 1;
	}

	for (int i = 0; i < n; i++) printf("%d\n", result_arr[i]);
	return 0;
}