Official Analysis (Polish)

Explanation

The number of inversions that result in joining two sets together is the sum of the inversions within the two sets plus the number of new inversions after joining the two sets, with each new inversion having one item in the left and right sets. Thus, to count the best way to merge the two sets, we need to find the inversions if we either swap or don't swap the two sets.

The implementation below uses small-to-large merging and ordered sets to efficiently count the least inversions we can have when combining the sets from our left and right subtrees. We iterate on the smaller set, and use the ordered set order_of_key method to count the number of elements $< x$ and $> x$, for every leaf value $x$ within the smaller set.

Implementation

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

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;