2465

Segment Tree를 공부한 후 풀지 못했던 문제들을 쏙쏙 해결하고 있다. 정보가 계속 업데이트 되며 거기서 특정한 값을 구해야 할 때 사용하기 유용한 자료구조이다. 줄세우기 문제 또한 그렇다. 

문제를 풀기 위한 전체적인 알고리즘은 주어진 키를 정렬 한 후 문제에서 주어진 수열의 맨 뒤 하나씩 확인한다. 현재의 정렬에서 주어진 값에 해당하는 index를 고르고(배열은 0부터 시작한다 그러면 앞에 주어진 값 만큼이 자신보다 작은게 있는게 확실해지므로) 선택한 키 값은 정렬에서 뺀다 그렇게하면 식이 하나밖에 성립되지 않을 것이다.

여기서 문제는 뒤에서 중간에 있는 것들을 선택하기 때문에 배열 자체가 계속 작아진다는 것이다. 이것을 해결하기 위해 어떻게할까 생각을 많이 했었는데 segment tree를 사용해서 해결 할 수 있었다. 참 무궁무진한 자료구조인듯하다..

 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>

using namespace std;

int s[400005];
int t[400005];
int h[100005];
int d[100005];
int r_idx[400005];

int N;

void build(int id=1, int l=0, int r=N){
	if(r-l<2){
		t[id]=1;
		r_idx[id]=r;
		s[id]=1;
		return;
	}

	int mid = (l+r)/2;
	build(id*2, l, mid);
	build(id*2+1, mid, r);

	s[id]=s[id*2] + s[id*2+1];
	r_idx[id]=r;
}

void modify(int p, int x, int id=1, int l=0, int r=N){
	s[id] += x-d[p];
	if(r-l<2){
		d[p]=0;
		s[id]=0;
		return;
	}

	int mid = (r+l)/2;
	if(p<mid)
		modify(p, x, id*2, l, mid);
	else
		modify(p, x, id*2+1, mid, r);
}

int main(){

	int line[100005];
	int res[100005];

	ifstream ifp("input.txt");


	ifp>>N;
	//scanf("%d", &N);
	
	for(int i=0; i<N; i++)
		ifp>>h[i];
		//scanf("%d", &h[i]);
	
	sort(&h[0], &h[N]);

	build(1, 0, N);

	for(int i=0; i<N; i++){
		ifp>>line[i];
		//scanf("%d", &line[i]);
		d[i]=1;
	}

	
	for(int idx=N-1; idx>=0; idx--){
		int size = line[idx];

		size++;
		int piv=1;
		
		int here;
		while(1){
			if(t[piv]){
				here = r_idx[piv]-1;
				break;
			}
			int l_child = piv*2;
			int r_child = piv*2+1;
			if(size <= s[l_child]){
				piv=l_child;
			}
			else{
				size -= s[l_child];
				piv=r_child;
			}
		}
		res[idx]=h[here];
		modify(here, 0, 1, 0, N);
		d[here]=0;
	}

	for(int i=0; i<N; i++)
		printf("%d\n", res[i]);

	return 0;

}