(1. 문제 설명)
https://www.acmicpc.net/problem/2517
(2차 솔루션)
첫 번째 좌표 압축
- 스킬 값은 10억 미만입니다.
- 그러나 지정 가능한 최대 날짜 수는 500,000개입니다.
- 또한 고유한 값으로 지정되어 있기 때문에 좌표압축을 통해 실제 메모리에 저장된다.
- 각 스킬의 순위를 확인할 수 있습니다.
반복 순서
- 마지막 위치에서 반복하여 능력이 낮은 사람의 수를 찾습니다.
=> 먼저 이런 식으로 섹션 트리를 만들고,
=> 섹션 트리에서 낮은 등급의 사람들의 능력을 점차적으로 제거해야 합니다. - 당신보다 앞서 있고 기술이 적은 사람들의 수를 찾기 위해 처음부터 반복하십시오.
=> 이런 식으로 빈 트리에서 시작
=> 높은 순위의 사람들의 기술을 점차적으로 추가하십시오. - 처음부터 반복하는 방식이 조금 더 좋아 보입니다.
- 한 방향으로만 반복한다는 사고방식에 빠지지 않는 것이 좋습니다.
(3번째 코드)