K Integers (Codeforces 1269E)
Tags: Others, binary search

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$.In one move you can swap two adjacent values.You want to perform a minimum number of moves, such that in the end there will exist a subsegment $$$1,2,\ldots, k$$$, in other words in the end there should be an integer $$$i$$$, $$$1 \leq i \leq n-k+1$$$ such that $$$p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k$$$.Let $$$f(k)$$$ be the minimum number of moves that you need to make a subsegment with values $$$1,2,\ldots,k$$$ appear in the permutation.You need to find $$$f(1), f(2), \ldots, f(n)$$$.

Input: The first line of input contains one integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$): the number of elements in the permutation.The next line of input contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$: given permutation ($$$1 \leq p_i \leq n$$$).

Output: Print $$$n$$$ integers, the minimum number of moves that you need to make a subsegment with values $$$1,2,\ldots,k$$$ appear in the permutation, for $$$k=1, 2, \ldots, n$$$.


Sample Inputs:
5
5 4 3 2 1

3
1 2 3

Sample Outputs:
0 1 3 6 10

0 0 0

Solution (Python):
from bisect import bisect_right, bisect_left

class BITbisect:

    def __init__(self, InputProbNumbers):
        self.ind_to_co = [-10 ** 18]
        self.co_to_ind = {}
        for (ind, num) in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind + 1
        self.max = len(self.co_to_ind)
        self.data = [0] * (self.max + 1)

    def __str__(self):
        retList = []
        for i in range(1, self.max + 1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return '[' + ', '.join([str(a) for a in retList]) + ']'

    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1 << i) <= self.max:
                if s + self.data[ind + (1 << i)] < key:
                    s += self.data[ind + (1 << i)]
                    ind += 1 << i
        if ind == self.max or key < 0:
            raise IndexError('BIT index out of range')
        return self.ind_to_co[ind + 1]

    def __len__(self):
        return self._query_sum(self.max)

    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0

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

    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError('The pushing number didnt initialized')
        self._add(self.co_to_ind[x], 1)

    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError('The deleting number didnt initialized')
        if self.count(x) <= 0:
            raise ValueError('The deleting number doesnt exist')
        self._add(self.co_to_ind[x], -1)

    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x] - 1)

    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i - 1)
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
Ind = [0] * (N + 1)
for (i, a) in enumerate(A):
    Ind[a] = i + 1
Bit = BITbisect(list(range(N + 1)))
ans = [0]
Bit.push(Ind[1])
a = 0
for n in range(2, N + 1):
    ind = Ind[n]
    f = Bit.bisect_left(ind)
    l = len(Bit)
    if l % 2 == 0:
        if f == l // 2:
            a += l // 2 - l // 2
        elif f < l // 2:
            p1 = Bit[l // 2 - 1]
            a += p1 - ind - 1 - (l // 2 - 1) + l - f
        else:
            p2 = Bit[l // 2]
            a += ind - p2 - 1 - (l // 2 - 1) + l - f
    else:
        p1 = Bit[l // 2]
        if f <= l // 2:
            a += p1 - ind - 1 - l // 2 + l - f
        else:
            a += ind - p1 - 1 - l // 2 + l - f
    ans.append(a)
    Bit.push(ind)
print(*ans, sep=' ')

Solution (Python):
class Fenwick:

    def __init__(self, max_val):
        self.b = [0] * (max_val + 1)

    def update(self, i, increment):
        while i > 0 and i < len(self.b):
            self.b[i] += increment
            i += i & -i

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

    def at_sum(self, k):
        (a, b) = (0, len(self.b))
        while a < b:
            mid = (a + b) // 2
            if k <= self.sum(mid):
                b = mid
            else:
                a = mid + 1
        return a

def solve(p):
    pos = [0] * len(p)
    for (i, e) in enumerate(p):
        pos[e - 1] = i + 1
    ans = 0
    fenwick = Fenwick(len(p))
    for i in range(1, len(p) + 1):
        p = pos[i - 1]
        fenwick.update(p, 1)
        r = fenwick.sum(p)
        m = (i + 1) // 2
        if r <= m:
            m = m + (i % 2 == 0)
            ans += fenwick.at_sum(m) - p - m + 1 + i - r
        else:
            ans += p - fenwick.at_sum(m) + m - r
        yield ans
input()
a = [int(_) for _ in input().split()]
print(*solve(a))

Solution (Python):
n = int(input())
arr = list(map(int, input().split()))
trees = [0] * (1 + n)
dic = [0] * (n + 1)
ans = [0] * n

def update(t, i, v):
    while i < len(t):
        t[i] += v
        i += lowbit(i)

def lowbit(x):
    return x & -x

def sum(t, i):
    ans = 0
    while i > 0:
        ans += t[i]
        i -= lowbit(i)
    return ans

def getmid(arr, l1, flag):
    (low, high) = (1, n)
    if l1 % 2 == 0 and flag:
        midv = l1 // 2
    else:
        midv = l1 // 2 + 1
    while low <= high:
        mid = (low + high) // 2
        ret = sum(arr, mid)
        if ret >= midv:
            high = mid - 1
        else:
            low = mid + 1
    return low
for i in range(n):
    dic[arr[i]] = i + 1
for i in range(1, n + 1):
    ans[i - 1] += sum(trees, n) - sum(trees, dic[i])
    if i >= 2:
        ans[i - 1] += ans[i - 2]
    update(trees, dic[i], 1)
visited = [0] * (1 + n)
mid = 0
last = 0
for i in range(1, n + 1):
    update(visited, dic[i], 1)
    mid = getmid(visited, i, dic[i] > mid)
    tt = sum(visited, dic[i])
    minus = min(tt - 1, i - tt)
    tmp = abs(dic[i] - mid - (tt - sum(visited, mid))) - minus
    ans[i - 1] += tmp + last
    last = tmp + last
print(' '.join(map(str, ans)))