지난 UCPC 2022에 PBDS가 나왔다.
몰랐던 자료구조니까 공부하긴 했는데 이게 생각보다 강력한 것 같다.
C++에서 지원하는데 이게 있으면 세그트리를 안짜도 된다.(근데 짜는게 맘편하긴 하다.)
감사한 곳
https://codeforces.com/blog/entry/11080
일단 g++에서만 가능하다고 한다.(unfortunately only for the GNU C++)
개념적으로는 set(map)인데 순서를 기록한다고 한다.
특정 수가 몇번째로 큰지, 특정 수보다 작은 수가 몇개 있는지를 구할 수 있는 내장 자료구조이다.
사용하려면 헤더를 따로 인클루드 하고 네임스페이스도 쓰고 타입도 정해야 한다.
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
null_type이 있는 부분에 타입을 지정하게 되면 map같이 쓸 수 있다.(value의 타입)
null_type으로 남겨 놓으면 set으로 사용하게 된다.
less는 비교 함수이다. less로 놓으면 오름차순 정렬이 된다.
내림차순으로 하려면 greater를 쓰면 된다.
rb_tree_tag는 기반이 되는 자료구조이다.
스플레이 트리나 ordered-vector 트리(???)가 있지만 작성자 왈 대회에서는 레드블랙트리만 사용할 수 있다고 한다.(속도이슈)
"Sadly, at competitions we can use only red-black trees"
이제 사용법을 알아보자.
기본적으로 rb트리를 사용한다고 했으니 삽입, 삭제, 값이 있는지 확인은 $O(\log n)$일 것이다.
핵심 메소드가 두개 있다.
find_by_order : 비교함수를 기준으로 정렬했을 때 n번째 오는 값을 리턴한다. (0-based index)
order_of_key : n과 자료구조 안에 있는 각 값을 비교함수에 넣었을 때 true를 반환하는 원소의 개수를 리턴한다.
비교함수를 less라고 하자.
find_by_order(n)은 n번째로 작은 값을 리턴한다.
order_by_key(n)은 n보다 작은 값의 개수를 리턴한다.
글 작성자가 측정한 시간이 있는데 세그트리보단 느리지만 $O(\log n)$시간에 수행하는 것 같다.(상수 차이인듯?)
사용 예시
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int main(){
ordered_set X;
X.insert(16);
X.insert(1);
X.insert(4);
X.insert(2);
cout<<*X.find_by_order(0)<<endl; // 1
cout<<*X.find_by_order(1)<<endl; // 2
cout<<*X.find_by_order(2)<<endl; // 4
cout<<*X.find_by_order(3)<<endl; // 16
cout<<*X.find_by_order(-1)<<endl; // 0 : 부적절한 인덱스
cout<<*X.find_by_order(5)<<endl;
cout<<X.order_of_key(1)<<endl; // 1보다 작은 원소 개수 : 0
cout<<X.order_of_key(4)<<endl; // 4보다 작은 원소 개수 : 2
cout<<X.order_of_key(400)<<endl; // 400보다 작은 원소 개수 : 4
}
간단하게만 살펴봤는데도 편리하고 사기적인 자료구조라는 것을 알 수 있다.
이를 사용하면 많은 어려운 문제를 직접 구현하지 않고도 해결할 수 있을 것이다.
(그런데 UCPC 2022예선 D를 푸는 방법은 아직 안떠오른다.)
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] Codeforces Round #811 (Div. 3) (0) | 2022.08.02 |
---|---|
[알고리즘] UCPC 2022 본선 후기 (2) | 2022.07.26 |
[알고리즘] UCPC 2022 예선 후기 (0) | 2022.07.04 |
[알고리즘] 파이썬 dict, C++ map/unordered_map (0) | 2022.06.15 |
[알고리즘] 고속 푸리에 변환(Fast Fourier Transform) part. 1 (0) | 2022.06.03 |