jh05013   6년 전

가장 잘 알려진 해법은 "머지소트 트리를 만들고 이분탐색으로 쿼리를 해결"인 것 같은데, 정작 트리 단계부터 분할 정복 단계보다 밑에 있고, 이분 탐색은 더 밑에 있으며, 구간 트리는 거의 맨 밑에 있습니다. 이 문제보다 나중에 나오는 알고리즘으로 브루트포스, BFS/DFS, 다익스트라 등이 있습니다.

꼭 이 방법만 써야 하느냐 하면 그것도 아닙니다. 분할 정복을 안 쓰는, 빠르고 간단한 O(NM) 풀이도 통과됩니다. (Pypy) (C++) 퀵셀렉으로 풀 수 있다면야 분할정복이겠지만, 범위가 세고 퀵셀렉이 무거워서 안 될 것으로 예상됩니다. 어느 쪽이든 이 단계에 어울려 보이지 않습니다.

startlink   5년 전

지웠습니다.

댓글을 작성하려면 로그인해야 합니다.