https://codeforces.com/blog/entry/9204
이 글의 댓에 따르면
구간에서 k번째로 작은 원소 찾는게 로그제곱 시간에 된다는데 이게 어케 되는건지 이해가 안됨
분할 정복으로 못 구하는 쿼리인데 로그 제곱만에 어케 되는거지
설명 가능하신분 있음?
이 글의 댓에 따르면
구간에서 k번째로 작은 원소 찾는게 로그제곱 시간에 된다는데 이게 어케 되는건지 이해가 안됨
분할 정복으로 못 구하는 쿼리인데 로그 제곱만에 어케 되는거지
설명 가능하신분 있음?
어떤 수가 구간에서 몇 번째인지 구하는 데 로그시간 걸리니까 그거로 파라메트릭 서치 돌리면 로그제곱이지
전체에서 그러면 로그제곱으로 되는데 구간에서 하려면 머지소트트리 쿼리 1번에 로그제곱으로 총 로그세제곱 아닌가요
아그렇네
코드보니까 머지소트트리를 a[i]가 아니라 pos[i]로 만드네 pos[i] = i번째로 큰 값의 위치 이건 좌표압축해서 만들면 되고
쿼리를 날릴 때 머지소트트리의 루트부터 보니까 시작 범위는 [0,N-1]임 여기서 왼쪽 절반 구간(자식노드)에서 pos가 [l,r]에 속하는 개수(cnt)를 구해 (머지소트트리에서 pos가 정렬되어 있으니까 이걸 이분탐색) cnt가 k보다 크거나 같으면 왼쪽 절반 구간에 답이 있으니까 왼쪽 구간으로 이동 작으면 오른쪽 절반 구간에 답이 있으니까 k=k-cnt하고 오른쪽 구간으로 이동
https://www.acmicpc.net/problem/7469
애초에
저 문제는 풀이가 많고 좀 알려져 있어서 이 문제번호로 검색하면 많이 나옴
어렵네...계속 생각해보겠음 ㄱㅅ
세그처럼 구간 logN개로 쪼개고 각 구간에서 이분탐색 -> 로그제곱
parallel binary search 공부하러 ㄱㄱ
Value로 머지소트트리를 만드는게 아니라 정렬된 value들에 대한 position으로 만들면 어떤 정렬된 value 구간에 i ~ j에 속한 값의 개수를 upperbound(j) - lowerbound(i)로 로그에 구할 수 있음. [0,n)에서 시작해서 이 개수가 k 이하면 왼쪽 구간으로 내려가고 초과면 오른쪽 구간으로 내려가면 (이 경우 왼쪽 구간에 속한 수를 빼줌) 정확히 k번째 value에 도달함.