Apparently this paper proves that this runs in O(nlog⁡n)\mathcal{O}(n\log n).

C++

int n;
ll ans, inv;
typedef struct tnode *pt;
struct tnode {
	int pri, val;
	pt c[2];  // essential
	int sz;   // for range queries
	tnode(int val) {
		pri = rng();
		val = val;

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.
Make code work and add explanation

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum