Optimal Insertion (Codeforces 1601C)
Tags: Greedy, 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
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')
(a, b, c, d, p) = ([], [], [], [], [])

def calc_p(a1, a2, b1, b2):
    m = (b1 + b2) // 2
    (x, s, ms, mp) = (b[m], 0, 0, a1 - 1)
    for i in range(a1, a2 + 1):
        if a[i] > x:
            s += 1
        if a[i] < x:
            s -= 1
        if s < ms:
            ms = s
            mp = i
    p[m] = mp
    if m > b1:
        calc_p(a1, mp, b1, m - 1)
    if m < b2:
        calc_p(max(a1, mp), a2, m + 1, b2)

def s(a, b):
    if a == b:
        return 0
    mid = (a + b) // 2
    r = s(a, mid) + s(mid + 1, b)
    (i, j, t) = (a, mid + 1, 0)
    while i <= mid and j <= b:
        if c[i] <= c[j]:
            d[t] = c[i]
            t += 1
            i += 1
        else:
            r += mid + 1 - i
            d[t] = c[j]
            t += 1
            j += 1
    for x in range(i, mid + 1):
        d[t] = c[x]
        t += 1
    for x in range(j, b + 1):
        d[t] = c[x]
        t += 1
    for x in range(a, b + 1):
        c[x] = d[x - a]
    return r
for _ in range(int(sys.stdin.readline())):
    import time
    tt = time.time()
    (n, m) = [int(i) for i in sys.stdin.readline().split()]
    a = [int(i) for i in sys.stdin.readline().split()[:n]]
    b = [int(i) for i in sys.stdin.readline().split()[:m]]
    b.sort()
    p = [0] * (m + 1)
    p[-1] = -2
    calc_p(0, n - 1, 0, m - 1)
    c = []
    j = 0
    while p[j] == -1:
        c.append(b[j])
        j += 1
    for i in range(n):
        c.append(a[i])
        while p[j] == i:
            c.append(b[j])
            j += 1
    d = [0] * (m + n)
    print(s(0, m + n - 1))

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):
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)