BOJ 2517 - 달리기

링크: https://www.acmicpc.net/problem/2517

문제

최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다.

"왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.

문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.

문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.

N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.

선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다.

코드

비슷한 문제

• BOJ 2336 - 굉장한 학생