Codeup/코드업 3180 간단한 문제 풀기 위해 공부 했던 것들

코드업 3180

간단한 문제

https://codeforces.com/blog/entry/52477     qoo2p5 의 말이 핵심 

How to find frequency of a given element in a range? - Codeforces

 

https://codeforces.com/blog/entry/11080  Index 있는 set을 사용할 수 있다.

C++ STL: Policy based data structures - Codeforces

 

나는  map<(value) , Indexed set>을 만들어서 upperbound(r) -lowerbound(l) 로 쿼리하고 insert & delete 로 update 해서 문제를 해결했다.

 

첨언하자면, mp[val].order_of_key(L) 로 indexed set 내에서 L의 lowerbound를 구할 수 있다.

upperbound의 경우는 어떻게 구할지 생각해보기 바란다.

 

---

참고 링크

맨 아래 '가장 유사한 문제' 와 Square Root Decomposition이 제일 중요하다.

Square Root Decomposition은 써먹을 때가 많으니 꼭 익히자.

 

*비슷한 의문을 가진 사람

https://codeforces.com/blog/entry/52578

 

*유사한 문제

https://www.geeksforgeeks.org/range-queries-for-frequencies-of-array-elements/ 

 

https://www.geeksforgeeks.org/maximum-occurrence-given-range/

 

https://www.geeksforgeeks.org/number-of-elements-greater-than-k-in-the-range-l-to-r-using-fenwick-tree-offline-queries/ 

 

(업데이트 x 버전) https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/ 

 

 

 

*가장 유사한 문제

(업데이트 버전) https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-2-including-updates/?ref=rp 

 

 

정책 기반 자료구조 없이 해결하려면 [ L ,R ] 에서 k 보다 큰 수 개수 구하고, k보다 작은 수 개수 구하는 방법으로도 해결 가능할 듯 하다.

https://www.geeksforgeeks.org/queries-for-elements-greater-than-k-in-the-given-index-range-using-segment-tree/?ref=rp  

업데이트가 가능할까..? 

Merge sort tree에서 1개의 원소를 바꾸는 경우 시간 복잡도 O(logn)에 해결 가능한 걸로 알고 있다.

 

아래 자료구조도 재밌어 보인다.

 

https://rachitiitr.blogspot.com/2017/06/wavelet-trees-wavelet-trees-editorial.html

Introduction to a New Data Structure: WAVELET TREES