[toph.co] C++ Vector Simulation

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : C++ Vector Simulation
Source            : toph.co
Category          : Data Structure
Algorithm         : Policy Based Data Structure, Disjoint Set Union
Verdict           : Accepted

#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;
 
static const int maxn = 1e5 + 5;
 
template <typename T> using orderedSet = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int father[maxn];
orderedSet <int> X[maxn];
 
inline void makeSet()
{
      for (int i = 1; i < maxn; i++)
      {
            father[i] = i;
            X[i].clear();
            X[i].insert(i);
      }
}
 
inline int findRep(int r)
{
      if (father[r] == r) return r;
      return father[r] = findRep(father[r]);
}
 
inline void Union(int u, int v)
{
      int p = findRep(u);
      int q = findRep(v);
      if (p == q) return;
      father[q] = p;
      for (auto &it : X[q]) X[p].insert(it);
}
 
inline int Med(int p)
{
      int f = findRep(p);
      int len = X[f].size();
      int k = (len-1)/2;
      int ans = *X[f].find_by_order(k);
      if (len%2==0) ans += *X[f].find_by_order(k+1);
      else ans *= 2;
      return ans;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int n, q;
            cin >> n >> q;
            makeSet();
            cout << "Case " << tcase << ":\n";
            while (q--)
            {
                  int type;
                  cin >> type;
                  if (type==1)
                  {
                        int x, y;
                        cin >> x >> y;
                        Union(x, y);
                  }
                  else
                  {
                        int x;
                        cin >> x;
                        cout << Med(x) << "\n";
                  }
            }
      }
}