Optimal Insertion (Codeforces 1602E)
Tags: Others, divide and conquer

You are given two arrays of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_m$$$.You need to insert all elements of $$$b$$$ into $$$a$$$ in an arbitrary way. As a result you will get an array $$$c_1, c_2, \ldots, c_{n+m}$$$ of size $$$n + m$$$.Note that you are not allowed to change the order of elements in $$$a$$$, while you can insert elements of $$$b$$$ at arbitrary positions. They can be inserted at the beginning, between any elements of $$$a$$$, or at the end. Moreover, elements of $$$b$$$ can appear in the resulting array in any order.What is the minimum possible number of inversions in the resulting array $$$c$$$? Recall that an inversion is a pair of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$c_i > c_j$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ for all tests cases in one input doesn't exceed $$$10^6$$$. The sum of $$$m$$$ for all tests cases doesn't exceed $$$10^6$$$ as well.

Output: For each test case, print one integer — the minimum possible number of inversions in the resulting array $$$c$$$.

Note: Below is given the solution to get the optimal answer for each of the example test cases (elements of $$$a$$$ are underscored).  In the first test case, $$$c = [\underline{1}, 1, \underline{2}, 2, \underline{3}, 3, 4]$$$.  In the second test case, $$$c = [1, 2, \underline{3}, \underline{2}, \underline{1}, 3]$$$.  In the third test case, $$$c = [\underline{1}, 1, 3, \underline{3}, \underline{5}, \underline{3}, \underline{1}, 4, 6]$$$. 

Sample Inputs:
3
3 4
1 2 3
4 3 2 1
3 3
3 2 1
1 2 3
5 4
1 3 5 3 1
4 3 6 1

Sample Outputs:
0
4
6

Solution (Python):
import os
import sys
import getpass
from collections import deque
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().rstrip('\r\n')
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
    if OFFLINE_TEST:
        print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
    if OFFLINE_TEST:
        log('----- solving ------')
        log(*args)
        log('----- ------- ------')
    return solve_(*args)

def read_matrix(rows):
    return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
    return [input().strip() for _ in range(rows)]

def minus_one(arr):
    return [x - 1 for x in arr]

def minus_one_matrix(mrr):
    return [[x - 1 for x in row] for row in mrr]

def solve(ans, a_s, a_e, b_s, b_e):
    if b_e < b_s:
        ans[a_s + b_s:a_e + b_e + 1 + 1] = aa[a_s:a_e + 1]
    else:
        b_mid = (b_e + b_s) // 2
        pos = a_s
        min_score = 0
        curr_score = 0
        for i in range(a_s, a_e + 1):
            if aa[i] > bb[b_mid]:
                curr_score += 1
            elif aa[i] < bb[b_mid]:
                curr_score -= 1
                if curr_score < min_score:
                    min_score = curr_score
                    pos = i + 1
        ans[b_mid + pos] = bb[b_mid]
        solve(ans, a_s, pos - 1, b_s, b_mid - 1)
        solve(ans, pos, a_e, b_mid + 1, b_e)

def mergeSort(arr):
    n = len(arr)
    temp_arr = [0] * n
    return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right) // 2
        inv_count += _mergeSort(arr, temp_arr, left, mid)
        inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count

def merge(arr, temp_arr, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += mid - i + 1
            k += 1
            j += 1
    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1
    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1
    for loop_var in range(left, right + 1):
        arr[loop_var] = temp_arr[loop_var]
    return inv_count
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    aa = list(map(int, input().split()))
    bb = sorted(list(map(int, input().split())))
    ans = [0 for i in range(n + m)]
    solve(ans, 0, n - 1, 0, m - 1)
    print(mergeSort(ans))

Solution (Python):
import os
import sys
import getpass
from collections import deque
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().rstrip('\r\n')
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
    if OFFLINE_TEST:
        print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
    if OFFLINE_TEST:
        log('----- solving ------')
        log(*args)
        log('----- ------- ------')
    return solve_(*args)

def read_matrix(rows):
    return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
    return [input().strip() for _ in range(rows)]

def minus_one(arr):
    return [x - 1 for x in arr]

def minus_one_matrix(mrr):
    return [[x - 1 for x in row] for row in mrr]

def mergeSort(arr):
    n = len(arr)
    temp_arr = [0] * n
    return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right) // 2
        inv_count += _mergeSort(arr, temp_arr, left, mid)
        inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count

def merge(arr, temp_arr, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += mid - i + 1
            k += 1
            j += 1
    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1
    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1
    for loop_var in range(left, right + 1):
        arr[loop_var] = temp_arr[loop_var]
    return inv_count

def solve_(arr, brr):
    irr = [0 for _ in arr]

    def binary_insert(sa, ea, sb, eb):
        if sa > ea:
            return
        ma = (sa + ea) // 2
        cur = 0
        for mb in range(sb, eb):
            if brr[mb] < arr[ma]:
                cur += 1
        best = cur
        best_pos = sb
        for mb in range(sb, eb):
            if brr[mb] > arr[ma]:
                cur += 1
            if brr[mb] < arr[ma]:
                cur -= 1
            if cur < best:
                best = cur
                best_pos = mb + 1
        irr[ma] = best_pos
        binary_insert(sa, ma - 1, sb, best_pos)
        binary_insert(ma + 1, ea, best_pos, eb)
    binary_insert(0, len(arr) - 1, 0, len(brr))
    res = []
    j = 0
    for (i, x) in enumerate(arr):
        while j < irr[i]:
            res.append(brr[j])
            j += 1
        res.append(x)
    while j < len(brr):
        res.append(brr[j])
        j += 1
    log(res)
    res = mergeSort(res)
    return res
for case_num in range(int(input())):
    (a, b) = list(map(int, input().split()))
    brr = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    arr.sort()
    res = solve(arr, brr)
    print(res)

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class Bit:

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def inversion(a, flag=True):
    n = len(a)
    if flag:
        b = [(a[i] << 30) + i + 1 for i in range(n)]
        b.sort()
        mask = (1 << 30) - 1
        a = [i & mask for i in b]
    bit = Bit(n)
    cnt = 0
    for i in range(n):
        bit.add(a[i], 1)
        cnt += i + 1 - bit.sum(a[i])
    return cnt

def f(li, ri, lp, rp):
    if li >= ri:
        return
    mid = (li + ri) // 2
    d = rp - lp + 1
    left = [0] * d
    for i in range(d - 1):
        if a[lp + i] > b[mid]:
            left[i + 1] = 1
        left[i + 1] += left[i]
    right = [0] * d
    for i in range(d - 2, -1, -1):
        if a[lp + i] < b[mid]:
            right[i] = 1
        right[i] += right[i + 1]
    for i in range(d):
        res = left[i] + right[i]
        if res <= mn[mid]:
            mn[mid] = res
            p[mid] = lp + i
    f(li, mid, lp, p[mid])
    f(mid + 1, ri, p[mid], rp)
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    b.sort()
    p = [0] * m
    mn = [10 ** 9] * m
    f(0, m, 0, n)
    c = [0] * (n + m)
    now = 0
    for i in range(n):
        while now != m and p[now] == i:
            c[i + now] = b[now]
            now += 1
        c[i + now] = a[i]
    while now < m:
        c[n + now] = b[now]
        now += 1
    print(inversion(c))