K Integers (Codeforces 1268C)
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):
import heapq

class DynamicMedian:

    def __init__(self):
        self.l_q = []
        self.r_q = []
        self.l_sum = 0
        self.r_sum = 0

    def add(self, val):
        if len(self.l_q) == len(self.r_q):
            self.l_sum += val
            val = -heapq.heappushpop(self.l_q, -val)
            self.l_sum -= val
            heapq.heappush(self.r_q, val)
            self.r_sum += val
        else:
            self.r_sum += val
            val = heapq.heappushpop(self.r_q, val)
            self.r_sum -= val
            heapq.heappush(self.l_q, -val)
            self.l_sum += val

    def median_low(self):
        if len(self.l_q) + 1 == len(self.r_q):
            return self.r_q[0]
        else:
            return -self.l_q[0]

    def median_high(self):
        return self.r_q[0]

    def minimum_query(self):
        res1 = len(self.l_q) * self.median_high() - self.l_sum
        res2 = self.r_sum - len(self.r_q) * self.median_high()
        return res1 + res2

class BIT:

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

    def add(self, i, val):
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

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

    def sum(self, i, j):
        return self._sum(j) - self._sum(i)
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
bit = BIT(n)
dm = DynamicMedian()
memo = {}
for i in range(n):
    memo[a[i] - 1] = i
b = [0] * n
for i in range(n):
    dm.add(memo[i])
    b[i] = dm.minimum_query() - (i + 1) ** 2 // 4
ans = [0] * n
tmp = 0
for i in range(len(a)):
    bit.add(memo[i], 1)
    tmp += bit.sum(memo[i] + 1, n)
    ans[i] = tmp + b[i]
print(*ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, cnt) = ([-1], [-1], [0])
    return (G0, G1, cnt)

def insert(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G1[j] = len(cnt) - 1
            j = G1[j]
        else:
            if G0[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G0[j] = len(cnt) - 1
            j = G0[j]
    cnt[j] += 1
    return

def count_max(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not k & pow2[i]:
            if G1[j] ^ -1:
                ans += cnt[G1[j]]
            j = G0[j]
        else:
            j = G1[j]
    return ans

def kth_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not G0[j] == -1 and cnt[G0[j]] >= k:
            j = G0[j]
        else:
            ans += pow2[i]
            if not G0[j] == -1:
                k -= cnt[G0[j]]
            j = G1[j]
    return ans

def fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
n = int(input())
p = list(map(int, input().split()))
x = [0] * (n + 1)
for i in range(n):
    x[p[i]] = i + 1
pow2 = [1]
l = 20
for _ in range(l):
    pow2.append(2 * pow2[-1])
(G0, G1, cnt) = binary_trie()
tree = fenwick_tree(n + 5)
ans = []
r = 0
(c1, c2) = (0, 0)
(d1, d2) = (0, 0)
for i in range(1, n + 1):
    xi = x[i]
    r += count_max(xi, l)
    ans.append(r)
    insert(xi, l)
    add(xi, xi)
    m = kth_min((i + 1) // 2, l)
    s1 = get_sum0(m - 1)
    s2 = get_sum(m + 1, n + 3)
    ans[-1] += c1 * m - s1 - d1
    ans[-1] += s2 - c2 * m - d2
    if i % 2:
        c2 += 1
        d2 += c2
    else:
        c1 += 1
        d1 += c1
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree:

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

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

    def get(self, i):
        return self.sum_range(i, i)

    def sum(self, i):
        ret = 0
        while i:
            ret += self.data[i]
            i &= i - 1
        return ret

    def sum_range(self, l, r):
        return self.sum(r) - self.sum(l - 1)

    def lower_bound(self, w):
        if w <= 0:
            return 0
        i = 0
        k = 1 << self.n.bit_length()
        while k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k >>= 1
        return i + 1
n = int(input())
a = list(map(int, input().split()))
d = {j: i for (i, j) in enumerate(a)}
BIT1 = Binary_Indexed_Tree(n)
BIT2 = Binary_Indexed_Tree(n)
BIT3 = Binary_Indexed_Tree(n)
tentou = 0
ans = []
for i in range(n):
    tmp = 0
    p = d[i + 1]
    inv_p = n - p
    tentou += BIT1.sum(inv_p)
    BIT1.add(inv_p, 1)
    BIT2.add(p + 1, 1)
    BIT3.add(p + 1, p + 1)
    m = i // 2 + 1
    mean = BIT2.lower_bound(i // 2 + 1)
    tmp = 0
    if i % 2 == 0:
        tmp -= m * (m - 1)
    else:
        tmp -= m * m
    tmp += tentou
    left = BIT3.sum_range(1, mean)
    right = BIT3.sum_range(mean, n)
    if i % 2 == 0:
        left = mean * m - left
        right = right - mean * m
    else:
        left = mean * m - left
        right = right - mean * (m + 1)
    tmp += left + right
    ans.append(tmp)
print(*ans)