[알고리즘] PBDS

지난 UCPC 2022에 PBDS가 나왔다.

몰랐던 자료구조니까 공부하긴 했는데 이게 생각보다 강력한 것 같다.

C++에서 지원하는데 이게 있으면 세그트리를 안짜도 된다.(근데 짜는게 맘편하긴 하다.) 

 

감사한 곳

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

C++ STL: Policy based data structures - Codeforces

일단 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를 푸는 방법은 아직 안떠오른다.)