Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

The Number of Inversions

  For a given sequence $A = \{a_0, a_1, ... a_{n-1}\}$, the number of pairs $(i, j)$ where $a_i > a_j$ and $i < j$, is called the number of inversions. The number of inversions is equal to the number of swaps of Bubble Sort defined in the following program:

bubbleSort(A)
  cnt = 0 // the number of inversions
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] < A[j-1]
	swap(A[j], A[j-1])
	cnt++

  return cnt

  For the given sequence $A$, print the number of inversions of $A$. Note that you should not use the above program, which brings Time Limit Exceeded.

Input

  In the first line, an integer $n$, the number of elements in $A$, is given. In the second line, the elements $a_i$ ($i = 0, 1, .. n-1$) are given separated by space characters.

output

  Print the number of inversions in a line.

Constraints

$ 1 \leq n \leq 200,000$

$ 0 \leq a_i \leq 10^9$

$a_i$ are all different

Sample Input 1

5
3 5 2 1 4

Sample Output 1

6

Sample Input 2

3
3 1 2

Sample Output 2

2



Sample input:
5
3 5 2 1 4


Sample output:
6

Submission status: Accepted

Solution code:
INF = 10**10


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(INF)
    rry.append(INF)

    cnt = 0
    i = 0
    j = 0
    for k in range(left, right):
        if lry[i] <= rry[j]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1
            cnt += len(lry) - 1 - i

    return cnt


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    n = int(input())
    ary = [int(_) for _ in input().split()]
    print(merge_sort(ary, 0, n))

Submission status: Accepted

Solution code:
cnt = 0
def merge(A,left,mid,right):
    global cnt
    n1 = mid - left
    n2 = right - mid

    L = [A[i] for i in range(left, mid)]
    R = [A[i] for i in range(mid, right)]
    L.append(float("inf"))
    R.append(float("inf"))
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            cnt += n1 - i
            A[k] = R[j]
            j += 1

def mergeSort(A,left,right):
        if left + 1 < right:
            mid = (left+right) // 2
            mergeSort(A,left,mid)
            mergeSort(A,mid,right)
            merge(A,left,mid,right)

input()
a = list(map(int, input().split()))
mergeSort(a, 0, len(a))
print(cnt)

Submission status: Accepted

Solution code:
count = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = A[left: left + n1], A[mid: mid + n2]
    global count

    L.append(2000000000)
    R.append(2000000000)

    i, j = 0, 0
    for k in range(left, right):
        #print("k", k, "l", left, "m", mid, "r", right, "L", L, "R", R)
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            count += len(L) - 1 - i
            j += 1


def mergeSort(A, left, right):
    #print("l", left, "r", right)
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


n = int(input())
input_list = list(map(int, input().split(' ')))

mergeSort(input_list, 0, n)
print(count)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    INF = int(1e+11)
    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 0

    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            if l[i] != INF:
                ans += mid - left - i

    return ans


def merge_sort(a, left, right):
    ans = 0
    if left + 1 < right:
        mid = (left + right) // 2
        ans += merge_sort(a, left, mid)
        ans += merge_sort(a, mid, right)
        ans += merge(a, left, mid, right)
        # print(left, right, ans)
    return ans

n = int(input())
a = [int(x) for x in input().split()]

print(merge_sort(a, 0, len(a)))

Submission status: Accepted

Solution code:
# Binary Indexed Tred
# https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree
# http://hos.ac/slides/20140319_bit.pdf
# https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree


from collections import defaultdict
import sys
input = sys.stdin.readline


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

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

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


def solve(n, A):
    ans = 0
    bit = FenwickTree(n)
    B = sorted(A)

    d = defaultdict(int)
    for i in range(n):
        d[B[i]] = i

    for i in range(n):
        t = A[i]
        ind = d[t] + 1
        ans += i - bit.sum(ind)
        bit.add(ind, 1)

    return ans


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = solve(n, A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
A = [int(x) for x in input().split()]
cnt = 0

def Merge(S, l, m, r):
    global cnt
    L = S[l:m] + [float('inf')]
    R = S[m:r] + [float('inf')]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] < R[j]:
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            cnt += len(L) - 1 - i
            j += 1
    return

def MergeSort(S, l, r):
    if r - l > 1:
        m = (l + r) // 2
        MergeSort(S, l, m)
        MergeSort(S, m, r)
        Merge(S, l, m, r)
    return

MergeSort(A, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
from collections import defaultdict
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

def solve():
  ans = 0
  N = int(input())
  bit = BIT(N)
  A = list(map(int, input().split()))
  dic = {a:i+1 for i,a in enumerate(sorted(A))}
  for i in range(N):
    A[i] = dic[A[i]]
  for i in range(N):
    ans += i - bit.sum(A[i])
    bit.add(A[i],1)
  return ans
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
S = [*map(int, input().split())]
t = [0]

def merge(A, left, mid, right):
  L = A[left:mid] + [float("inf")]
  R = A[mid:right] + [float("inf")]
  i, j = 0, 0
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      t[0] += mid + j - k
      j += 1
  return right - left

def merge_sort(A, left, right):
  count = 0
  if right - left > 1:
    mid = (left + right) // 2
    count += merge_sort(A, left, mid) + merge_sort(A, mid, right)
    count += merge(A, left, mid, right)
  return count

count = merge_sort(S, 0, n)
print(t[0])

Submission status: Accepted

Solution code:
count = 0

#in: list1 int
#global count
def merge(list1, list2):
    global count
    output = []
    p1 = 0
    p2 = 0
    l1 = len(list1)
    l2 = len(list2)
    while p1<l1 and p2<l2:
        num1 = list1[p1]
        num2 = list2[p2]
        if num1 <= num2:
            output.append(num1)
            p1 += 1
        else:
            output.append(num2)
            p2 += 1
            count += l1 - p1
    return output+list1[p1:]+list2[p2:]

#counting_merge_sort
#in: list1
def counting_merge_sort(list1):
    if len(list1) <= 1:
        return list1
    pivot = len(list1)//2
    return merge(counting_merge_sort(list1[:pivot]), counting_merge_sort(list1[pivot:]))

n = int(input())
list1 = list(map(int, input().split(' ')))
counting_merge_sort(list1)
print(count)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    n = NI()
    A = LI()
    S = sorted(A)

    bit = [0] * (n+1)

    def bit_add(i,x):
        while i <= n:
            bit[i] += x
            i += i & (-i)

    def bit_sum(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & (-i)
        return ret

    ans = 0
    for i,x in enumerate(A):
        z = bisect.bisect_left(S,x) + 1
        bit_add(z,1)
        ans += z - bit_sum(z)
    print (ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in list(input().split())]
B = [[A[i], i + 1] for i in range(n)]
B.sort()
A = [j for i, j in B]
bit = [0] * (n + 2)
ans = 0
for i in range(n):
    ret = 0
    a = A[i]
    while 0 < a:
        ret += bit[a]
        a -= a & (-a)
    ans += i - ret
    a = A[i]
    while a <= n:
        bit[a] += 1
        a += a & (-a)
print(ans)

Submission status: Accepted

Solution code:
def merge(a,left,mid,right):
    count=0
    L=a[left:mid]+[float("inf")]
    R=a[mid:right]+[float("inf")]
    i,j=0,0
    for k in range(left,right):
        if L[i]<=R[j]:
            a[k]=L[i]
            i+=1
        else:
            a[k]=R[j]
            j+=1
            count+=mid-left-i
    return count

def mergeSort(a,left,right):
    if left+1<right:
        mid=(left+right)//2
        countl=mergeSort(a,left,mid)
        countr=mergeSort(a,mid,right)
        countm=merge(a,left,mid,right)
        return countm+countl+countr
    return 0



n=int(input())
a=[int(i)for i in input().split()]
ans=mergeSort(a,0,n)
print(ans)

Submission status: Accepted

Solution code:
num = int(input())
arr = list(map(int, input().split()))

num_of_inversions = 0

def merge(arr, left, middle, right, count):
    global num_of_inversions

    L = arr[left:middle]
    L.append(float('inf'))
    R = arr[middle:right]
    R.append(float('inf'))

    offset = len(L) - 1 + left
    countL, countR = 0, 0

    iterL, iterR = iter(L), iter(R)
    l,r = next(iterL), next(iterR)

    for index in range(left, right):
        count += 1
        if l <= r:
            arr[index] = l
            l = next(iterL)
            countL += 1
        else:
            arr[index] = r
            r = next(iterR)
            num_of_inversions += countR - index + offset
            countR += 1
    return count

def merge_sort(arr, left, right, count):
    if left + 1 < right:
        pivot = (left + right) // 2
        count = merge_sort(arr, left,  pivot, count)
        count = merge_sort(arr, pivot, right, count)

        count = merge(arr, left, pivot, right, count)
    return count

_ = merge_sort(arr, 0, num, 0)
print(num_of_inversions)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = [0] * (n1 + 1), [0] * (n2 + 1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    L[n1] = float('INF')
    R[n2] = float('INF')

    i, j = 0, 0
    reverse_cnt = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            reverse_cnt += n1 - i
            A[k] = R[j]
            j += 1
    return reverse_cnt


def merge_sort(A, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(A, left, mid)
        cnt += merge_sort(A, mid, right)
        cnt += merge(A, left, mid, right)
    return cnt


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    q = merge_sort(A, 0, N)
    print(q)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def invr(x):
    if len(x)<=1:
        return x,0
    m=len(x)
    x1=x[:m//2]
    x2=x[m//2:]
    x11,r1=invr(x1)
    x22,r2=invr(x2)
    x11=x11[::-1]
    x22=x22[::-1]
    rx=[];r=r1+r2
    while x11 and x22:
        if x11[-1]<=x22[-1]:
            rx.append(x11.pop())
        else:
            rx.append(x22.pop())
            r+=len(x11)
    rx+=x11[::-1]
    rx+=x22[::-1]
    return rx,r
n=int(input())
*a,=map(int, input().split())
_,ans=invr(a)
print(ans)

Submission status: Accepted

Solution code:
from math import inf


def merge(A, left, mid, right):
    global count

    L = A[left: mid]
    R = A[mid: right]

    L.append(inf)
    R.append(inf)

    i = 0
    j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            count += mid - left - i


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def main():
    global count
    n = int(input())
    A = list(map(int, input().split()))

    merge_sort(A, 0, n)
    print(count)


if __name__ == "__main__":
    count = 0
    main()

Submission status: Accepted

Solution code:
#反転数(sumは1から始めるやつ)

import bisect

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
c = sorted(a)

for i in range(n):
    d = bisect.bisect(c,a[i])
    b[i] = d

data = [0] * (n+1)

def init(k,x):
    while k <= n:
        data[k] += x
        k += k & -k
        
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
    
ans = 0
for i in range(n-1,-1,-1):
    init(b[i],1)
    ans += get(b[i]-1)

print(ans)

Submission status: Accepted

Solution code:
import math

_ = input().rstrip()
A = list(map(int, input().rstrip().split(" ")))

cnt = 0

def merge(A, left, mid, right):
    global cnt
    L, R = [], []
    for a in A[left:mid]:
        L.append(a)
    for a in A[mid:right]:
        R.append(a)
    L.append(math.inf)
    R.append(math.inf)
    
    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += len(L) - 1 - i
            
            
def mergeSort(A, left, right):
    if right - left > 1:
        mid = (right + left) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
mergeSort(A, 0, len(A))
print(cnt)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**7)
input= lambda:sys.stdin.readline().rstrip()
N=int(input())
class BIT:
    # 1,,,,,,,Nまでの数値を扱える
    def __init__(self,n):
        self.n=n
        self.data=[0]*(n+1)
    def to_sum(self,i):
        # i番目のところまで要素を足し合わせる
        s=0     
        while i>0:
            s+=self.data[i]
            i-=(i& -i)
        return s
    def add(self,i,x):
        # i 番目のところに要素を足し合わせる
        while i<=self.n:
            self.data[i]+=x
            i+=(i & -i)
    def get(self,i,j):
        #i番目からj番目までの要素の合計値を数える
        return self.to_sum(j)-self.to_sum(i-1)
ans = 0

A=list(map(int,input().split()))
B=sorted(A)
how_big={B[i]:i+1 for i in range(N)}
tree = BIT(N+100)

for index, p in enumerate(A):
    tree.add(how_big[p], 1)
    #自分よりも左側にある（小さい）の数を求める。
    ans += index+1-tree.to_sum(how_big[p])
print(ans)

Submission status: Accepted

Solution code:
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 main():
    N = int(input())
    *A, = map(int, input().split())

    compress_dict = {x: i for i, x in enumerate(sorted(set(A)), start=1)}
    M = len(compress_dict)

    bit = Bit(M)
    ans = 0
    for cnt, x in enumerate(A, start=1):
        x = compress_dict[x]
        bit.add(x, 1)
        ans += cnt - bit.sum(x)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]

z = 0
c = 0

def merge(A, left, right):

    global c, z

    n1 = (right - left) // 2 + left  # L側の個数

    L = A[left:n1]
    R = A[n1:right]

    L.append(INF)
    R.append(INF)

    # print(L, R)

    i = 0
    j = 0
    l = len(L)
    for k in range(left, right):
        z += 1

        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            # print(l-i-1)
            c += l-i-1


def mergesort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, right)


mergesort(A, 0, N)

# print(" ".join([str(x) for x in A]))
# print(z)
print(c)

Submission status: Accepted

Solution code:
class BIT:
    ''' binary indexed tree '''
    def __init__(self, size):
        self.size = size
        self.bit = [0] * (size + 1) # 1 indexed
    def add(self, pos, x):
        ''' bit の pos の位置に x を加える '''
        while pos <= self.size:
            self.bit[pos] += x
            pos += self.right_most_bit(pos)
    def sum(self, pos):
        ''' bit の 1...pos の和を返す '''
        ans = 0
        while pos > 0:
            ans += self.bit[pos]
            pos -= self.right_most_bit(pos)
        return ans
    def right_most_bit(self, x):
        return x & -x

n = int(input())
a = list(map(int, input().split()))

# a の各要素から(順位-1)へ map する辞書を作る
aa = sorted(a)
d = {k:v for v, k in enumerate(aa)}
b = BIT(n)

cnt = 0
index = 0
for ai in a:
    cnt += index - b.sum(d[ai])
    b.add(d[ai]+1, 1)
    index += 1

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
ソートテク関連の基本的な関数の詰め合わせ (命名は C++ STL algorithm による)


stable_partition(seq, func):
    O(n)
    空間計算量も O(n)
    述語が True を返す全ての要素が、述語が False を返す全ての要素よりも前になるようにシーケンスを並び替える (破壊、安定)


nth_element(seq, k, begin, end):
    O(n)
    E = seq[k] とする
    特定の要素 E よりも小さい全ての要素が E よりも前になり、 E 以上の全ての要素がEよりも後になるように seq[begin:end] を並び替える (破壊、不安定)
    heapq の nlargest とは異なるので注意


ith_order_statistic(seq, i, begin, end):
    O(n)
    nth_element を用いて (seq[begin:end] に存在することがわかっている) i 番目の順序統計量を求める (i = 0, 1, ..., n-1)


simple_quick_sort(seq, begin, end):
    O(nlgn)
    nth_element を用いて seq[begin:end] をソートする (破壊、不安定)


modified_merge_sort(seq, begin, end):
    O(nlgn)
    _modified_merge を用いて seq[begin:end] をソートする (非破壊、安定)
    転倒数とソート済み配列を返す


count_inversion(seq):
    O(nlgn)
    modified_merge_sort を用いて seq の転倒数を求める
    (転倒数: seq[i] > seq[j] (i < j) なる (i, j) の組み合わせの数のこと)
"""


import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]




def _modified_merge(left: List[Num], right: List[Num]) -> Tuple[int, List[Num]]:
    """
    ソート済み配列 left, right を受け取り、全体のソート済み配列を生成する (O(n))
    マージの過程で転倒数をメモして返す

    Args:
        left (list): ソート済み
        right (list): ソート済み

    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> _modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])
    """
    sorted_list = []
    i, j, inv = 0, 0, 0
    buf_1 = left[:] + [float('inf')]
    buf_2 = right[:] + [float('inf')]
    for _ in range(len(left) + len(right)):
        if buf_1[i] < buf_2[j]:
            sorted_list.append(buf_1[i])
            i += 1
            inv += j
        else:
            sorted_list.append(buf_2[j])
            j += 1
    return inv, sorted_list


def modified_merge_sort(L, begin, end):
    """
    L[begin:end] を 非破壊的かつ安定にマージソートする (O(nlgn))
    マージソートの過程で転倒数をメモして返す

    Args:
        L (list)
        begin, end (int)
    
    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])
    """
    if end - begin == 1:
        return 0, [L[begin]]
    mid = (begin + end) // 2
    left_inv_cnt, left = modified_merge_sort(L, begin, mid)
    right_inv_cnt, right = modified_merge_sort(L, mid, end)
    merge_inv_cnt, sorted_list = _modified_merge(left, right)
    return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list


def count_inversion(L):
    """
    modified_merge_sort() を用いて L の要素の転倒数を求める (O(nlgn))

    Examples:
        >>> count_inversion([1, 9, 2, 7, 5, 6, 4, 8, 3, 0])
        26
    """
    cnt, _ = modified_merge_sort(L, 0, len(L))
    return cnt


if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    print(count_inversion(L))

Submission status: Accepted

Solution code:
def merge(cnt, A, left, mid, right):
    L = A[left:mid] + [2147483648]
    R = A[mid:right] + [2147483648]
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            cnt.append(j)
        else:
            A[k] = R[j]
            j += 1
            
def mergeSort(cnt, A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(cnt, A, left, mid)
        mergeSort(cnt, A, mid, right)
        merge(cnt, A, left, mid, right)
        
        
import sys
def input():
    return sys.stdin.readline()[:-1]
    
n = int(input())
S = list(map(int, input().split()))

from collections import deque
cnt = deque()
mergeSort(cnt,S,0,n)

print(sum(cnt))

Submission status: Accepted

Solution code:
def merge(A, l, m, r):
    cnt = 0  
    n1 = m-l 
    n2 = r-m  

    L = A[l:m]  
    L.append(float("inf")) 
    R = A[m:r]
    R.append(float("inf")) 

    i_l, i_r = 0, 0  
    for k in range(l, r):
        if L[i_l] <= R[i_r]:
            A[k] = L[i_l]
            i_l += 1
        else:
            A[k] = R[i_r]
            i_r += 1
            cnt += n1 - i_l  
    return cnt


def merge_sort(A, l, r):
    if l + 1 >= r:  
        return 0

    m = (l+r)//2
    ans1 = merge_sort(A, l, m)  
    ans2 = merge_sort(A, m, r)
    ans3 = merge(A, l, m, r)  

    return ans1 + ans2 + ans3


n = int(input())
A = list(map(int, input().split()))
print(merge_sort(A, 0, n))

Submission status: Accepted

Solution code:
class BIT_dinamic: #0-indexed
    def __init__(self, n):
        self.tree = {}
        self.MAX = n
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            if i in self.tree:
                s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.MAX:
            if i in self.tree:
                self.tree[i] += x
            else:
                self.tree[i] = x
            i += i & -i

   
###########################################
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
a = [int(i) for i in readline().split()]

sA = sorted(a)
# def zaatu(x): return bisect_left(sA, x) #xの圧縮先
# def modosu(i): return sA[i]  # 逆写像

b = BIT_dinamic(n)

from bisect import *
ans = 0
for i,ai in enumerate(a):
    j = bisect_left(sA, ai)
    ans += i - b.get_sum(j)
    b.add(j,1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    S = LI()

    def merge_cnt(A, left, mid, right):
        L = A[left:mid]
        R = A[mid:right]
        L.append(INF)
        R.append(INF)
        i = 0
        j = 0
        cnt = 0
        for k in range(left, right):
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                A[k] = R[j]
                cnt += (mid - left) - i
                j += 1
        return cnt

    def rec(A, left, right):
        if left+1 < right:
            mid = (left+right)//2
            l_cnt = rec(A, left, mid)
            r_cnt = rec(A, mid, right)
            m_cnt = merge_cnt(A, left, mid, right)
            return l_cnt+r_cnt+m_cnt
        else:
            return 0

    print(rec(S, 0, n))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
MAX = 2*10**5
SENTINEL = 2*10**9
L = [0]*(MAX//2 + 2)
R = [0]*(MAX//2 + 2)

def Merge(A,n,left,mid,right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    
    L[n1] = SENTINEL
    R[n2] = SENTINEL
    i,j = 0,0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1
            cnt += n1 - i
    return cnt

def MergeSort(A,n,left,right):
    if left + 1 < right:
        mid = (left + right)//2
        v1 = MergeSort(A,n,left,mid)
        v2 = MergeSort(A,n,mid,right)
        v3 = Merge(A,n,left,mid,right)
        return v1 + v2 + v3
    else:
        return 0

if __name__ == "__main__":
    n = int(input())
    A = list(map(int,input().split()))
    ans = MergeSort(A,n,0,n)
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
nums=list(map(int,input().split()))
count=0

def inversions(nums,left,mid,right):
    global count
    inf=10**9
    L=nums[left:mid]+[inf]
    R=nums[mid:right]+[inf]
    i=0
    j=0
    l=len(L)-1
    for k in range(left,right):
        if L[i]<=R[j]:
            nums[k]=L[i]
            i+=1
            l-=1

        else:
            nums[k]=R[j]
            j+=1
            count+=l


def inversions_sort(nums,left,right):
    if left+1<right:
        mid=(left+right)//2
        inversions_sort(nums,left,mid)
        inversions_sort(nums,mid,right)
        inversions(nums,left,mid,right)



inversions_sort(nums,0,n)
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class BinaryIndexedTree():

    def __init__(self,init_val):
        self.bit = [0] + init_val
        self.n  = len(init_val)

    def sum(self,i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret
    
    def add(self,i,x):
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

def main():
    N = int(input())
    A = list(map(int,input().split()))
    B = sorted(A)
    dic = {b:i for i,b in enumerate(B,1)}
    bit = BinaryIndexedTree([0]*N)
    ans = 0
    for i,a in enumerate(A):
        ans += i - bit.sum(dic[a])
        bit.add(dic[a],1)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
inf = 1000000001

def merge(A,left,mid,right):
	L = A[left:mid] 
	n1 = len(L)
	L += [inf]
	R = A[mid:right] + [inf]
	i = 0
	j = 0
	cnt = 0
	
	for k in range(left,right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
			cnt += n1 - i
	return cnt

def mergeSort(A,left,right):
	if left + 1 < right:
		mid = (left + right) // 2
		v1 = mergeSort(A,left,mid)
		v2 = mergeSort(A,mid,right)
		v3 = merge(A,left,mid,right)
		return v1 + v2 + v3
	else:
		return 0
	

n = int(input())
A = list(map(int, input().split()))

#cnt = 0
n_ivs = mergeSort(A,0,n)
#print(*A)
#print(cnt)
print(n_ivs)

Submission status: Accepted

Solution code:
n = int(input())
S = [int(i) for i in input().split()]
infty = 10**10
cnt = 0
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = A[left:mid] + [infty]
    R = A[mid:right] + [infty]
    
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        if(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            if(L[i] != infty):
#                 print("LR", L[i], R[j])
                cnt += len(L) - 1  - i
#     print(cnt)
            
def mergeSort(A, left, right):
    if (left + 1 < right):
        mid = int((left + right)/2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
mergeSort(S, 0, len(S))
# print(" ".join([str(st) for st in S]))
print(cnt)

Submission status: Accepted

Solution code:

import sys

sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline


def inpS(): return inp().rstrip().decode()


readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
INF = 1 << 60

# ---------------------------------------------------
# ---------------------------------------------------
# ---------------------------------------------------

cnt = 0
def resolve():
    def merge(l, r):
        global cnt
        mA = []
        l_i = 0
        r_i = 0
        while l_i < len(l) and r_i < len(r):
            if l[l_i] <= r[r_i]:
                mA.append(l[l_i])
                l_i += 1
            else:
                mA.append(r[r_i])
                r_i += 1
                # Lの個数から今のL_indを引けばRより大きい個数がわかる
                cnt += len(l) - l_i
        # 残りを加える
        if l_i < len(l):
            mA.extend(l[l_i:])
        elif r_i < len(r):
            mA.extend(r[r_i:])
        return mA

    def mergesort(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = mergesort(arr[:mid])
        right = mergesort(arr[mid:])

        return merge(left, right)

    N = int(inp())
    A = list(map(int, inp().split()))

    mergesort(A)
    print(cnt)

if __name__ == '__main__':
    resolve()