jh20s   4년 전

예를들어
1 2 3 4 5 6 에서 4번째를  뽑아라 -> 4

1 2 3 5 6에서   4번째를 봅아라 ->  5

1 2 3 6 

이런 것 입니다.


벡터의 erasae를 이용- > 선형시간이라 안되고,

map , set은 이진탐색트리이긴 하나 각각 L,R 부트리 사이즈를 알 수 있는 함수는 없으니 안될 것 같습니다.


그렇다면 직접 부트리의 개수를 반환하는 균형 이진탐색트리를 만들던가

이중연결리스트를 구현해서 이진탐색하는 그런방법말고는 O(lgN)으로 알 수 있는 방법이 없을까요?? 


dlwodnsdl   4년 전

세그먼트 트리를 만들어 주고, 각각의 노드에 남은 수를 값으로 넣어주면 O(lgN)만에 가능하지 않을까요?

jh20s   4년 전

이진탐색트리 구현이 너무 길어 이걸 외워야하나 했는데 공부하고 알려주신 sqrt decomposition도 더 공부해야겠네요 ㅠㅠ...

jh20s   4년 전

세그도 좋은방법같네요 한번 도전해봐야겠어요 ㅎㅎ 

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