XOR Inverse
Contest: Codeforces Round 673 (Div. 1)
Difficulty rating: 2000
Tags: bitmasks, data structures, divide and conquer, dp, greedy, math, sortings, strings, trees

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. You have to choose a non-negative integer $$$x$$$ and form a new array $$$b$$$ of size $$$n$$$ according to the following rule: for all $$$i$$$ from $$$1$$$ to $$$n$$$, $$$b_i = a_i \oplus x$$$ ($$$\oplus$$$ denotes the operation bitwise XOR).

An inversion in the $$$b$$$ array is a pair of integers $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le n$$$ and $$$b_i > b_j$$$.

You should choose $$$x$$$ in such a way that the number of inversions in $$$b$$$ is minimized. If there are several options for $$$x$$$ — output the smallest one.

Input format:
First line contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of elements in $$$a$$$.

Second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

Output format:
Output two integers: the minimum possible number of inversions in $$$b$$$, and the minimum possible value of $$$x$$$, which achieves those number of inversions.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first sample it is optimal to leave the array as it is by choosing $$$x = 0$$$.

In the second sample the selection of $$$x = 14$$$ results in $$$b$$$: $$$[4, 9, 7, 4, 9, 11, 11, 13, 11]$$$. It has $$$4$$$ inversions:

- $$$i = 2$$$, $$$j = 3$$$;
- $$$i = 2$$$, $$$j = 4$$$;
- $$$i = 3$$$, $$$j = 4$$$;
- $$$i = 8$$$, $$$j = 9$$$.

In the third sample the selection of $$$x = 8$$$ results in $$$b$$$: $$$[0, 2, 11]$$$. It has no inversions.

Example input:
4
0 1 3 2

Example output:
1 0

Example input:
9
10 7 9 10 7 5 5 3 5

Example output:
4 14

Editorial:
Note: the integer $$$x$$$ from the statement is marked as an uppercase $$$X$$$ for clarity.
Take any arbitrary integers $$$x$$$ and $$$y$$$. It is a well-known fact that whether $$$x < y$$$ or $$$x > y$$$ depends only on one bit — the highest bit which differs in both.
So, let's construct a trie on our array integers. Represent each number as a binary string from the highest bit ($$$29$$$) to the lowest bit ($$$0$$$). Each leaf will keep a corresponding index/indices from the array and each non-leaf node will have at most two children — one for $$$0$$$-edge and one for $$$1$$$-edge.
Let's denote $$$S(v)$$$ as a sorted list of indices of all values in the subtree of $$$v$$$. These lists can be easily maintained while inserting our numbers into trie. Take any arbitrary vertex $$$v$$$ which has both children and has a depth (distance from root) of $$$k$$$. Let $$$a$$$ and $$$b$$$ be its children. Here comes the most important thing to notice: If the $$$k$$$-th highest bit of $$$X$$$ is toggled, lists $$$S(a)$$$ and $$$S(b)$$$ will change their relative order. Otherwise, it will not change. Thus, exploiting the fact that both lists are sorted, we can efficiently calculate the corresponding number of inversions between those lists and add them to our values $$$sum[k][0]$$$ and $$$sum[k][1]$$$. $$$sum[i][j]$$$ means the number of inversions we have to add if $$$i$$$-th highest bit of $$$X$$$ is equal to $$$j$$$.
After the calculation of our $$$sum$$$ table is done, the value of $$$X$$$ can be easily restored.
Time complexity: $$$O(n \log 10^9)$$$
Memory complexity: $$$O(n \log 10^9)$$$