요약
Order Statistic Tree(이하 pbds)는 다음 연산을 O(logN)에 처리할 수 있다. 다만 상수가 조금 크다.
- K번째 원소 찾기
- 주어진 원소의 순서 구하기
위의 연산이 필요하면 일단 pbds를 들이대보자.
TLE가 발생하면 좌표 압축 + Fenwick Tree로 처리하자.
연습 문제
1. Cookie Selection
pair<int, int> pbds
2. Galactic Collegiate Programming Contest
tuple<int, int, int> pbds
3. Baby Names
string pbds
끝
끝
'알고리즘' 카테고리의 다른 글
Euler's phi function (0) | 2022.10.05 |
---|---|
Union-Find (0) | 2022.10.04 |
Fenwick Tree (0) | 2022.09.30 |
Knuth's Optimization (0) | 2022.09.28 |
유클리드 알고리즘 관련 정리 (0) | 2022.09.26 |