글 읽기 - 트리와 k번째수 11932

HJY 7년 전 0

트리와 k 번째수 문제에서

HLD + Parametric 으로 꾸겨넣었는데...

쿼리하나당 처리해야 하는시간이 log * log * log 인것같아서...
좌표압축처리나, 아니면 트리를 balanced하게 잡도록 해서 시간을 줄여야하는건지..

아니면 제가 삽질하고있는건지... 힌트를 주시면 감사하겠습니다 .ㅠ.ㅠ.........

h0ngjun7 7년 전 1

persistent segment tree
http://blog.anudeep2011.com/persistent-segment-tre...

h0ngjun7 7년 전 1

HLD로도 풀 수 있을거에요 아마

HJY 7년 전 0

@appa

좋은 정보(persistent-segment-tree) 너무너무 감사드립니다.ㅠ
한번 공부를 해봐야할것같습니다.

그런데...
HLD을 이용하는 해법은
parametric으로 값을 찾는게 맞나요?

최적화 같은것은 안하고 꾸깃꾸깃 넣었는데, 다른 최적화를 하고 풀어야하는지 궁금합니다.

 while (l <= r) {
            int mid = (l + r) / 2;
            int aa = query_up(u, lca_v, mid);
            int bb = query_up(v, lca_v, mid);
            int cc = query_up(lca_v, lca_v, mid);
            int ret = aa + bb - cc;
 
            if (ret > (k - 1)) {
                r = mid - 1;
            }
            else {
                ans = mid;
                l = mid + 1;
            }
        }
        printf("%d\n", ans);

h0ngjun7 7년 전 0

작성하신 코드로 직접 제 데이터 가지고 수행해보니, init에서 시간이 아주 오래 걸리네요.

HJY 7년 전 0

@appa

감사합니다....
init에서 시간이 걸리는거면..답이없네요...ㅎㅎ;

가르쳐주신대로 해야할것 같네요.... 상세하게 가르쳐주셔서 감사합니다

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

문제

문제

출처

ICPC

트리와 k번째수 11932

HJY 7년 전 0

h0ngjun7 7년 전 1

h0ngjun7 7년 전 1

HJY 7년 전 0

h0ngjun7 7년 전 0

HJY 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말