wwiiiii   3달 전

세그먼트 트리에는 각 구간을 정렬시켜 저장하고, 쿼리가 들어오면 해당하는 구간들의 노드 번호를 query 함수로 찾은 다음, 가능한 수의 범위에서 parametric search를 이용해 답을 찾으려고 했는데 TLE가 나네요 ㅠㅠ 

query함수 시간복잡도가 logN, count 함수 시간복잡도가 log^2 N, parametric search하는데 log(최대원소값 - 최소원소값)인데 왜 시간 초과가 될까요?

jaydoubluel   3달 전

음수 binary search 할 때에는 조심해야 합니다

if(left + right >= 0) mid = (left + right) / 2; else mid = (left + right - 1)/2;

라던지..

wwiiiii   3달 전

고치니까 바로 되네요 ㅎㅎ

ljh6274   2달 전

참고하여 도움이 됐습니다. 감사합니다!

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