[백준/BOJ/1849] 순열

값이 없으면 0,

값이 있으면 1로 채워서 세그먼트 트리를 초기화 한 후에

k <= tree[node * 2] 로직에 의해서 tree[node*2] 는 sum 값이므로 sum 값이 k 와 같아지는 노드의 위치를 찾아낸다.

 

arr[i] + 1 을 해주는 이유는

값이 5일 경우, 앞에 더 큰 값이 5개가 있다는 의미이므로 6번째에 위치시켜야 하기 때문이다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAX = 1e5 + 1;
int tree[MAX * 3], arr[MAX], res[MAX];
void init(int node, int start, int end) {
	if (start == end) {
		tree[node] = 1;
		return;
	}
	init(node * 2, start, (start + end) / 2);
	init(node * 2 + 1, (start + end) / 2 + 1, end);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int node, int start, int end, int index, int diff) {
	if (index < start || index > end) return;
	if (start == end) {
		tree[node] = tree[node] + diff;
		return;
	}
	update(node * 2, start, (start + end) / 2, index, diff);
	update(node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int kth(int node, int start, int end, int k) {
	if (start == end) return start;
	if (k <= tree[node * 2]) {
		return kth(node * 2, start, (start + end) / 2, k);
	}
	else {
		return kth(node * 2 + 1, (start + end) / 2 + 1, end, k - tree[node * 2]);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	init(1, 1, N);  
	for (int i = 1; i <= N; i++) {
		int k = arr[i] + 1;
		int w = kth(1, 1, N, k);
		res[w] = i;
		update(1, 1, N, w, -1);
	}
	for (int i = 1; i <= N; i++) {
		cout << res[i] << "\n";
	}
	return 0;
}