[1321] 군인

https://www.acmicpc.net/problem/1321

 

세그먼트트리 문제다. 바로 이전 문제인 [2243] 사탕상자 문제와 동일한 풀이로 접근하면 된다.

 

풀이

N개의 부대에 속한 군인 수를 저장하는 구간 합 세그먼트트리를 생성한다. 이후 i번째 군인의 부대를 호출할 때, 현재 구간의 군인 수가 i보다 크다면 좌측노드에서 i번째 군인 탐색. 현재 구간의 군인 수가 i보다 적다면 (i - 좌측구간 군인수) 번째 군인을 우측노드에서 탐색한다. 없는 군인을 탐색하는 경우는 주어지지 않으므로 리프노드에 도달할 경우에 해당 노드의 인덱스를 반환하면 된다.

 

정답 코드