BOJ 2465 줄 세우기

난이도 : 플4 (사실 OST를 알고 있으면 날로 먹을 수 있다.)

 

문제 설명

사람들 $n$ 명의 키가 주어지고, 이들이 어떤 순서로 줄을 서 있는데, $\texttt{arr[i]}$ 는 $i$번 사람 앞에 $i$번보다 키가 작거나 같은 사람이 몇 명 서 있는지를 나타낸다. 이 정보에 맞는 순서를 construct하는 문제.

 

풀이

arr[n-1] 부터 거꾸로 배열을 만들어 나가자. n-1번, 즉 끝 번호에는 '나보다 키가 작거나 같은 사람의 수' 를 정확히 알고 있으므로, 정렬된 배열에서 arr[n-1]번째가 그냥 n-1번째의 키이다. 이제 이 사람보다 앞에 있는 사람들만 볼 것이므로, 이 사람을 집합에서 빼 버리고 다시 n-2번에 대해서 같은 작업을 수행하자.

 

즉, multiset 같은 자료구조가 있어서,

- 정렬된 상태에서 $t$ 번째 원소가 몇인지를 빠르게 알고

- 정렬된 상태를 유지하면서 $x$를 넣고 뺄 수 있는

- 중복을 허용하는

성질을 가지면 된다. 

 

세그먼트 트리를 이용해서 이런 쿼리를 처리할 수 있지만, GCC 컴파일러를 사용한다면 Order Statistics Tree가 정확히 이런 일을 해준다.

구체적으로, OST (Order Statistics Tree) 는 PBDS (Policy-Based Data Structure) 라이브러리에 들어 있는데, 다음을 지원한다.

- find_by_order(x) : 현재 들어 있는 원소들 중 $x$번째의 원소가 몇인지를 알 수 있다.

- order_of_key(x) : Lower bound 함수와 같다. 즉, 정렬성을 유지한 채로 넣을 수 있는 가장 작은 index를 반환한다. 만약 이미 있는 원소에 대해 order_of_key를 받아오면 실제 order이고, 중복을 허용하는 경우 그중 가장 앞 번호이다.

- insert, delete : 당연히 된다. 정렬성이 깨지지 않는다.

 

비록 상수가 조금 크긴 하지만 이 4가지 연산이 모두 $O(log n)$ 에 되고, 원래 Set Map Multiset 같은게 상수가 크니까 그걸 쓰는 문제들 시간 제한이 넉넉해서 대체로는 납득할만한 시간에 돈다. 

 

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

 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimization ("unroll-loops")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef tree<int, null_type, less_equal<int>,
        rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

ordered_multiset X;
vector <int> v;
vector <int> od;
int ans[101010];
int main()
{
	usecppio
	int n;
	cin >> n;
	for (int i = 0; i<n; i++)
	{
		int k;
		cin >> k;
		X.insert(k);
	}
	for (int i = 0; i<n; i++)
	{
		int u;
		cin >> u;
		od.push_back(u);
	}
	while(!od.empty())
	{
		int x = od.back();
		od.pop_back();
		int k = *(X.find_by_order(x));
		X.erase(X.upper_bound(k));
		v.push_back(k);
	}
	reverse(all(v));
	for (auto it:v) cout << it << '\n';
}