XOR Inverse (Codeforces 1416C)
Tags: Greedy, divide and conquer

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: 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: Output two integers: the minimum possible number of inversions in $$$b$$$, and the minimum possible value of $$$x$$$, which achieves those number of inversions.

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.

Sample Inputs:
4
0 1 3 2

9
10 7 9 10 7 5 5 3 5

3
8 10 3

Sample Outputs:
1 0

4 14

0 8

Solution (Python):
def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    minInv = 0
    minX = 0
    batch = [list(range(n))]
    for i in range(29, -1, -1):
        bit = 1 << i
        dontToggleInv = 0
        toggleInv = 0
        nextBatch = []
        for group in batch:
            zeros = []
            ones = []
            for idx in group:
                if a[idx] & bit > 0:
                    ones.append(idx)
                    toggleInv += len(zeros)
                else:
                    zeros.append(idx)
                    dontToggleInv += len(ones)
            if len(zeros) > 1:
                nextBatch.append(zeros)
            if len(ones) > 1:
                nextBatch.append(ones)
        batch = nextBatch
        if dontToggleInv <= toggleInv:
            minInv += dontToggleInv
        else:
            minInv += toggleInv
            minX = minX | bit
    print('{} {}'.format(minInv, minX))
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
main()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def solve(a, k):
    cur = []
    nxt = []
    tot = 0
    inv = 0
    ct = 0
    nin = 0
    for i in a:
        if i & 1 << k:
            cur.append(i)
            nin += tot
            inv += len(a) - tot - ct
            ct += 1
        else:
            tot += 1
            nxt.append(i)
    inv -= ct * (ct + 1) // 2
    d1[k] = d1.get(k, 0) + inv
    d2[k] = d2.get(k, 0) + nin
    if k - 1 >= 0:
        if cur:
            solve(cur, k - 1)
        if nxt:
            solve(nxt, k - 1)
n = int(input())
a = list(map(int, input().split()))
d1 = dict()
d2 = dict()
solve(a, 31)
ans = 0
inv = 0
for i in d1:
    inv += min(d1[i], d2[i])
    if d1[i] > d2[i]:
        ans += 1 << i
print(inv, ans)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def print_list(l):
    print(' '.join(map(str, l)))
from collections import defaultdict as dc
n = N()
a = RLL()
res = 0
ans = 0
dic = dc(list)
for i in range(n):
    dic[a[i]].append(i)
t = list(sorted(dic.keys()))
dic = [[i] + dic[i] for i in t]

def merge(a, b):
    (inverse, i, j, na, nb) = (0, 1, 1, len(a), len(b))
    r = []
    while i < na and j < nb:
        if a[i] < b[j]:
            r.append(a[i])
            i += 1
        else:
            r.append(b[j])
            j += 1
            inverse += i - 1
    inverse += (i - 1) * (nb - j)
    r += b[j:]
    r += a[i:]
    return (inverse, (na - 1) * (nb - 1) - inverse, r)
k = 0
while len(dic) > 1:
    (x, y, i, nd) = (0, 0, 0, len(dic))
    nex = []
    while i < nd - 1:
        if dic[i][0] & 1 == 0 and dic[i + 1][0] == dic[i][0] + 1:
            (dx, dy, r) = merge(dic[i + 1], dic[i])
            x += dx
            y += dy
            nex.append([dic[i][0] >> 1] + r)
            i += 2
        else:
            dic[i][0] >>= 1
            nex.append(dic[i])
            i += 1
    if i == nd - 1:
        dic[i][0] >>= 1
        nex.append(dic[i])
    res += min(x, y)
    if x > y:
        ans |= 1 << k
    k += 1
    dic = nex
print(res, ans)