2021년 1월 17일 PS 일지 - K보다 작은 수의 개수 쿼리

클래스 7에 들어갔는데 재미있는 문제들이 보인다. -> "수열과 쿼리 1"

 

그중 예전에 풀었던 KQUERY와 연관된 문제가 여럿 있어 모두 AC를 띄우고 왔다.

달달하다~

 

K Query2 같은 경우 구간에서 k 이상인 수 개수 쿼리 + point update를 처리하는 문제인데 대부분 sqrt decomposition으로 풀었지만 내 풀이는 좌표압축 + BIT in Seg로 O( log^2 N)에 각 쿼리를 처리 가능하다. 하지만 시간은 웬지 모르게 평방분할보다 느리다. 세그가 복잡한 연산이여서 그렇다고 생각한다.
Geeks for Geeks 평방분할 풀이
- www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-2-including-updates/

Number of elements less than or equal to a given number in a given subarray | Set 2 (Including Updates) - GeeksforGeeks

 

알고리즘 공부는
cp - algorithm 
이곳만한 데가 없다.

굳이 다른데 찾느라 시간 낭비하지 말고 앞으로는 저기서 모르는거 위주로 쭈욱 공부해야겠다.

Mo's Algorithm 연습문제를 쭈욱 풀었다.
서다수쿼, 화려한마을2,3, Poklon, 수쿼5,6, 배열의 힘.

K번째 수 문제.
머지소트 트리 + 파라메트릭 서치로 O(lg^3 N)에 푸는게 존재한다.

내 풀이는 정렬 후 인덱스로 머지소트 트리를 만든 다음
k번째 수 구하기를 세그먼트 트리에서 O(lg N)에 하는 방법을 이용해
각 쿼리를 O(lg^2 N)에 처리한다.

똑같은 머지소트 트리이지만 lg N 항을 하나 뗄 수 있다는게 인상깊다.