c언어 12899번 데이터 구조 (백준)

#include <stdio.h> 

int tree[8000008]={};//segment tree

int find(int s, int e, int node, int cnt) { //탐색
	if(s==e) return s;
	int m = (s+e)/2;
	if(tree[node*2]>=cnt) find(s,m,node*2,cnt);
	else find(m+1,e,node*2+1,cnt-tree[node*2]);
}

void update(int s, int e, int node, int index, int dif) { //수정
	if(index < s || index > e) return;
	tree[node] += dif;
	if(s==e) return;
	int m = (s+e)/2;
	update(s,m,node*2,index,dif);
	update(m+1,e,node*2+1,index,dif);
}

int main(void) {
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++) { //query
		int a,b;
		scanf("%d %d",&a,&b);
		if(a==1) { //수정
			update(1,2000000, 1, b, 1);
		}
		else if(a==2) { //x번째로 작은 거 찾기 및 그것을 1개 제거
			b = find(1,2000000,1,b);
			printf("%d\n",b);
			update(1,2000000, 1, b, -1);
		}
	}
}

 

풀이 : 세그먼트 트리

 

https://h202.tistory.com/739

c언어 2243번 사탕상자 (백준)

 

이 문제와 같은 문제로 볼 수 있습니다.

 

segment tree로 데이터베이스를 구축 한 후 (1번 부터 2000000번까지 몇개가 들어있는지를)

 

X번째로 작은것을 꺼내는 것을 구현 할 때는

왼쪽 자식노드가 X개 이상 있다면 왼쪽 자식노드를 탐색

그렇지 않다면 오른쪽 자식노드에 있다는 의미이므로 오른쪽 자식노드를 탐색합니다.

단 오른쪽 자식노드를 탐색 할때는, 왼쪽 자식노드에 있는 누적합 만큼 빼주고 탐색을 이어가야 합니다.

(위의 find 함수에서 cnt가 x번째의 의미를 가지고 있습니다)

 

segment tree의 크기를 2000002 * 4 로 넉넉히 잡아 놓았지만 더욱더 줄일 수  있습니다.