풀 수 있는 방법이 여러가지가 있는데요

일단 대표적으로 아래와 같은 세가지 방법이 있습니다.

1. sqrt decomposition

2. segment tree

3. persistent segment tree

이 중 가장 쉽게 구현할 수 있는건 1번과 2번인데요, 구간의 정렬된 값들을 각각의 버킷이나 노드가 가지고 있도록

알고리즘을 설계하신다면 쉽게 해결할 수 있을겁니다.

@kesakiyo구간의 정렬된 값들을 모두 갖기엔 메모리가 너무 많이드는데 어떤식으로 가지고 있어야 하나요??

segment tree와 sqrt decomposition같은 경우 O(N^2)개의 구간의 정렬된 값을 모두 가질 필요가 없습니다.

따라서 메모리는 문제가 되지 않습니다.

@kesakiyo segment tree 로 풀려면 merge sort tree 를 만들어야 하는건가요?

merge sort tree라는 용어가 있는지는 잘 모르겠지만, 맞는 것 같습니다.

자식들부터 원소를 추가해 주고, 부모는 양쪽 자식이 이미 정렬된 값들을 가지고 있을 때 머지소트하듯이 선형 시간 안에 합쳐 자신의 정렬된 값을 만들 수 있고...

저는 그 방법으로 풀었습니다. 인터넷을 찾아봤지만요...

@kks227 그렇군요 감사합니다