zasxer   2달 전

소스 일부를 읽다가 궁금한 점이 있어 질문드립니다.

bt[i / 2].push_back(bt[i][i1++]);

bt[i][i1++]를 push_back하면 bt[i/2]에는 어떤 형식으로 들어가 있나요?

문제를 sqrt decomposition으로 풀었는데, segment tree를 활용하여

query를 보내고 받는 형식이던데 구동 방식이 어떻게 되나요?

제 코드랑 많이 비슷하네요!

위 코드를 통해 만들어지는 트리는 담당하는 구간을 소팅된 상태로 저장하는 세그먼트 트리입니다.

332cce5ab21144369f488c6cce65ced6.png

조악한 그림 죄송합니다.

위처럼 세그먼트 트리의 각 노드가 자신이 담당하는 구간을 정렬된 상태로 모두 저장하고 있습니다. 따라서 노드 하나는 정수 하나가 아니라 배열 하나로 표현됩니다.

공간복잡도가 O(nlogn)이 되며, 해당 문제에서는 일반적인 세그먼트 트리처럼 구간을 대표하는 노드들에서의 바이너리 서치를 통해

C 이하인 값이 K개 이상이 되는 최소의 C를 찾는 방식으로 K번째 수를 찾습니다.

zasxer   2달 전

감사합니다!!!!
코드가 비슷하다니용... 

portableangel님의 소스가 맞아용!!
소스보고 감탄에 감탄을...
태그하면 실례일 거 같아서 혹시나해서 코드를 살짝 몰래 올렸는데 죄송합니다...

 감사합니다ㅎㅎ

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