USACO Platinum 2017 January - Promotion Counting

Merging Indexed Sets

Time Complexity: $\mathcal{O}(N\log ^2N)$

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int MX = 1e5+5;

Recall from the module that std::swap(d[a],d[b]) will be too slow. However, the following does (overloading std::swap):

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int MX = 1e5+5;