백준 1849 - 순열(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1849

 

이분 탐색을 이용한 세그먼트 트리 문제입니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

int N;
int Tree[100001 * 4];
int remake[100001 * 4];
int Rank[100001 * 4];
int ans[100001 * 4];

void make_tree(int node, int st, int fin){
	if(st == fin) {
		Tree[node] = 1;
		return;
	}
	int left = node * 2;
	int right = node * 2 + 1;
	int mid = (st + fin) / 2;
	make_tree(left, st, mid);
	make_tree(right, mid + 1, fin);
	Tree[node] = Tree[left] + Tree[right];
}

void update_tree(int node, int st, int fin, int target, int idx){
	Tree[node]--;
	if(st == fin){
		ans[st] = idx;
		return;
	}
	int left = node * 2, right = node * 2 + 1;
	int mid = (st + fin) / 2;
	if(target <= Tree[left]){
		update_tree(left, st, mid, target, idx);
	}
	else{
		update_tree(right, mid + 1, fin, target - Tree[left], idx);
	}
}

void solve(){
	make_tree(1, 1, N);
	for(int i = 1; i <= N; i++){
		update_tree(1, 1, N, Rank[i] + 1, i);
	}
	for(int i = 1; i <= N; i++) cout << ans[i] << "\n";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++) scanf("%d", &Rank[i]);
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.