boj2465.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
 
using namespace std;
 
int indexTree[100001 * 4];
int p = 1;  
//트리가 몇층인지를 저장함
int Floor = 1;
 
//업데이트 함수
void update(int i, int value){
    //i는 바닥층에서 인덱스 번호
    //전체 트리에서 인덱스 변호로 변환
    int indexnumber = p + i;
     
    indexTree[indexnumber] = value;
 
    for (indexnumber >>= 1; indexnumber >= 1; indexnumber >>= 1)
        indexTree[indexnumber] = indexTree[indexnumber * 2] + indexTree[indexnumber * 2 + 1];
}
 
int findIndex(int wantnum){
    int index = 1;
     
    //1층 부터 한층씩 진입
    for (int i = 1; i <= Floor-1; i++){
        if (indexTree[index * 2] >= wantnum){
            index = index * 2;
        }
        else{
            wantnum -= indexTree[index * 2];
            index = index * 2 + 1;          
        }
    }
    return (index - p);
}
 
int main(){
    int N;  
    cin >> N;
 
    vector<int> heightSet(N);
    vector<int> heightArr(N);
    vector<int> result(N);
 
    for (int i = 0; i < N; i++)
        scanf("%d", &heightSet[i]);
    sort(heightSet.begin(), heightSet.end());
 
    for (int i = 0; i < N; i++)
        scanf("%d", &heightArr[i]);
     
    while (p < N){
        p <<= 1;
        Floor++;
    }
 
    //전처리할 구간 채우기
    for (int i = 0; i <= N - 1; i++)
        indexTree[p + i] = 1;
    //부모 노드에 계산 결과 저장
    for (int i = p-1; i >= 1; i--)
        indexTree[i] = indexTree[i * 2] + indexTree[i * 2 + 1];
     
    for (int i = N - 1; i>= 0; i--){
        int targetindex = findIndex(heightArr[i]+1);
        result[i] = heightSet[targetindex];
        update(targetindex, 0);
    }
 
    for (int i = 0; i < N; i++)
        printf("%d\n", result[i]);
     
    return 0;
}