백준 10293 - Ranks in groups (C++)

문제

• 문제 링크

  
   BOJ 10293 - Ranks in groups 
  

• 문제 요약

$N$명의 학생들을 대상으로 $Q$개의 쿼리를 처리하자.
쿼리는 두 종류로, 두 그룹을 $merge$ 하는 쿼리와 어떤 학생이 자신이 속한 그룹에서 몇 등인지 조사하는 쿼리다.

• 제한

TL : $5$ sec, ML : $256$ MB




$1 ≤ N ≤ 10^5$

$1 ≤ Q ≤ 2*10^5$

알고리즘 분류

• 자료 구조(data structures)
• 분리 집합(disjoint_set)
• 트리를 사용한 집합과 맵(tree _ set / map)
• 작은 집합에서 큰 집합으로 합치는 테크닉(smaller_to_larger)

풀이

집합 단위 $merge$가 수행되므로 분리 집합을 생각해 볼 수 있다.

$2$번 쿼리를 봤을 때, 나이브하게 $O(N)$으로 응답을 하면 $O(NQ)$로 $TLE$ 확정이라 좀 더 효율적으로 집합 내 요소들을 관리해야 했다.

정렬된 상태를 유지해야 하므로 $std::set$을 생각해 볼 수 있지만 특정 요소가 집합 내 몇 번째인지$?$를 빠르게 찾아내기 위해선 개선이 필요하다.

이때, 그동안 간혹 말로만 들었지 써먹어 본 적은 없었던 $PBDS$[ $Policy$ $Based$ $Data$ $Structures$ ]가 떠올랐다.

앞서 말하자면 이 친구는 $gcc$ 확장 라이브러리이다.

---

위 글과 적당한 구글링을 통해 사용법을 익힌 후 바로 코드를 작성해 보았다.

한가지 유의 사항으로, 문제의 정의에 따르면 그룹 내 등수 판정 기준은 내림차순으로 보아야 한다.
이에 따라, $PBDS$의 $Policy$로 $less$가 아닌 $greater$를 주어 기준을 맞춰주었다.

$1$번 쿼리.

그룹을 전이할 때, 항상 그룹의 크기가 작은 쪽에서 큰 쪽으로 합쳐주자.
이를 잡아주지 않고 그냥 진행하게 되면 최악의 경우 쿼리 당 $O(N)$의 연산을 소모하게 될 수 있기 때문이다.

그룹 $y$가 그룹 $x$로 전이될 때, $y_1, y_2,$ $...$ $y_k$에 대해 $par[y_k] = x$로 맞춰주는 것도 빼먹지 말자.

$2$번 쿼리.

$PBDS.order$_$of$_$key(x)$를 호출할 경우, $PBDS$에서 $x$보다 정렬 기준 상 앞선 요소들의 개수를 반환한다.

우리는 등수를 구해야 하므로, 위 값에 $+1$을 해주면 되겠다.

전체 코드

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define N 100001
 
using namespace std;
using namespace __gnu_pbds;
 
 
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> PBDS;
 
PBDS S[N];
int n, q, par[N];
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--)
    {
        for (int i{}; i < N; i++)
        {
            S[i].clear();
            S[i].insert(i);
            par[i] = i;
        }
 
        cin >> n >> q;
        for (int k, x, y; q--;)
        {
            cin >> k;
            if (k & 1)
            {
                cin >> x >> y;
                x = par[x], y = par[y];
                if (x ^ y)
                {
                    if (S[x].size() < S[y].size())
                        swap(x, y);
 
                    for (auto& i : S[y])
                    {
                        S[x].insert(i);
                        par[i] = x;
                    }
                }
            }
            else
            {
                cin >> x; y = par[x];
                cout << S[y].order_of_key(x) + 1 << '\n';
            }
        }
    }
}

comment

끝