[C++/g++] PBDS(Policy Based Data Structure)

매일 상상만 하던 random access + O(logN) 삽입 삭제가 이미 있다니 . . (only g++)

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main(){
	ordered_set oSet;
	// idx 번째 iterator 반환
	oSet.find_by_order(idx);

	// value의 idx를 반환 (value보다 작은 원소 개수를 반환)
	oSet.order_of_key(value);

	oSet.insert(v);
	oSet.erase(v);
}

 
 

활용

https://www.acmicpc.net/problem/2517

2517번: 달리기

정해는 (세그먼트 트리 + 값 압축) 이라고 알고 있는 문제이다. (본 내용과 다른 방법)
 
자신보다 앞에 달리는 사람중 자신보다 실력이 낮은 사람을 제외한 등수를 출력하면 되는 간단한 문제이지만, N이 50만이다.
 
Array에 이분탐색으로 실력이 낮은 사람이 몇 명인지 찾은 후 그 뒤에 삽입하면 될 것 같지만 ... (혹은 BST로)

• Array : 검색은 O(logN)이나, 삽입할 때마다 뒤에 있는 모든 노드가 밀리는 시간이 생긴다.
• Tree : 삽입은 O(logN)이나, 몇 명이 나보다 실력이 낮은지 빠르게 검색할 방법이 없다.

 
둘다 각자의 단점으로 시간초과가 나버린다.
 
이럴 때 PBDS에서 Tree-Based Containers 를 사용하면 된다.
삽입도 O(logN)에 가능하고 검색도 O(logN)에 가능하다.
 
아래와 같은 코드로 위의 문제를 해결할 수 있다.

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>;

ordered_set oSet;

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int n, t;
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		cin >> t;
		oSet.insert(t);
		cout << (i - oSet.order_of_key(t)) << " ";
	}
}

https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_based_containers.html