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:
import sys

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int, sys.stdin.readline().split()))
    b = compress(a)

    ft = FenwickTree(max(b) + 1)
    ans = 0

    for bi in reversed(b):
        ans += ft.psum(bi + 1)
        ft.add(bi, 1)

    print(ans)

def compress(a):
    n = len(a)
    a = [(ai, i) for i, ai in enumerate(a)]
    a.sort()

    num = -1
    p = -1

    b = [None] * n

    for val, idx in a:
        if val > p:
            num += 1

        b[idx] = num
        p = val

    return b

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

    def add(self, i, x):
        i += 1

        while i <= self.n:
            self.b[i] += x
            i += i & (-i)

    def psum(self, r):
        res = 0

        while r > 0:
            res += self.b[r]
            r -= r & (-r)

        return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

inf = 1<<30
ans = 0

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int, sys.stdin.readline().split()))

    MergeSort(a)

    print(ans)

def MergeSort(a):
    if len(a) == 1:
        return a

    apre = MergeSort(a[:len(a)//2])
    asuf = MergeSort(a[len(a)//2:])

    res = merge(apre, asuf)

    return res

def merge(a, b):
    global ans
    na = len(a)
    nb = len(b)

    a.append(inf)
    b.append(inf)

    la = 0
    lb = 0

    res = []

    for i in range(na + nb):
        if a[la] > b[lb]:
            ans += na - la
            res.append(b[lb])
            lb += 1
        else:
            res.append(a[la])
            la += 1

    return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your co
import math

def merge(left,right,mid,A):
    global cnt
    n1=mid-left
    n2=right-mid
    L=A[left:mid]
    R=A[mid:right]
    L.append(centi)
    R.append(centi)
    Li,Ri = 0, 0
    for k in range(left,right):
        if L[Li] <= R[Ri]:
            A[k]=L[Li]
            Li+=1
        else:
            A[k] =R[Ri]
            Ri+=1
            cnt += (n1)-Li
            
    
cnt = 0
centi = math.pow(10,10)

def mergesort(left, right , A):
    if left+1 < right:
        mid = (left+right)//2
        mergesort(left,mid,A)
        mergesort(mid,right,A)
        merge(left,right,mid,A)
        
        
Right=int(input())
N=list(map(int,input().split()))

mergesort(0,Right,N)
print(cnt)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    cnt_local = 0
    leftA = A[left:mid]
    rightA = A[mid:right]
    leftA.append(INF)
    rightA.append(INF)
    l = 0
    r = 0
    for i in range(left, right):
        if leftA[l] <= rightA[r]:
            A[i] = leftA[l]
            l += 1
        else:
            A[i] = rightA[r]
            r += 1
            cnt_local += len(leftA) - l - 1
    return cnt_local


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


if __name__ == "__main__":
    INF = 10000000000
    n = int(input())
    S = list(map(int, input().split()))
    num = 0
    cnt = mergeSort(S, 0, len(S))
    print(cnt)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global count
    # count += (right - left)
    L = A[left:mid] + [int(1e9)]
    R = A[mid:right] + [int(1e9)]
    i = 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 = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().strip().split()))
    count = 0
    merge_sort(A, 0, n)
    print(count)

Submission status: Accepted

Solution code:
def merge(S, left, mid, right):
	global cnt
	L = S[left:mid] + [float('inf')]
	R = S[mid:right] + [float('inf')]
	i,j = 0,0
	for k in range(left,right):
		if L[i] <= R[j]:
			S[k] = L[i]
			i += 1
		else:
			S[k] = R[j]
			j += 1
			cnt += mid - left - i


def merge_sort(S, left = 0, right = 200000):
	right = min(len(S),right)
	if left+1 < right:
		mid = (left+right) // 2
		cnt1 = merge_sort(S, left, mid)
		cnt2 = merge_sort(S, mid, right)
		cnt3 = merge(S, left, mid, right)


if __name__ == '__main__':
	n = int(input())
	A = [int(s) for s in input().split()]
	cnt = 0
	inv = merge_sort(A)
	print(cnt)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

count = 0
def merge(A, left, right, mid):
    L = [A[i] for i in range(left, mid)]
    R = [A[i] for i in range(mid, right)]
    L.append(10**9+1)
    R.append(10**9+1)
    i = 0
    j = 0
    global count
    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 mergeSort(A, left, right):
    if right > left + 1:
        mid = int((right + left) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, right, mid)
        

mergeSort(a, 0, n)
print count

Submission status: Accepted

Solution code:
MAX = 1000000001

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

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

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
#    print(A)
    cnt = mergeSort(A, 0, num, 0)
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def merge(A, l, m, r):
    L = A[l:m] + [10 ** 9 + 1]
    R = A[m:r] + [10 ** 9 + 1]
    i, j, p, q = 0, 0, 0, 0
    for k in range(l, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            q += p
        else:
            A[k] = R[j]
            j += 1
            p += 1
    global cnt
    cnt += q

def mergeSort(A, l, r):
    if r - l > 1:
        m = (l + r) // 2
        mergeSort(A, l, m)
        mergeSort(A, m, r)
        merge(A, l, m, r)

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

Submission status: Accepted

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

def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 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 += len(l) - i - 1

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

mergeSort(s, 0, n)

print(count)

Submission status: Accepted

Solution code:
def count(A,left, right):
    if left >= right:
        return 0
    mid = (left + right) // 2
    cl = count(A, left, mid)
    cr = count(A, mid+1, right)
    L = A[left:mid + 1]
    R = A[mid+1:right+1]
    c, m, n, k= 0, 0, 0, left
    while m < len(L) and n < len(R):
        if L[m] > R[n]:
            A[k] = R[n]
            k += 1
            c += (len(L) - m)
            n += 1
        else:
            A[k] = L[m]
            m += 1
            k += 1
    while m < len(L):
        A[k] = L[m]
        m += 1
        k += 1
    while n < len(R):
        A[k] = R[n]
        k += 1
        n += 1 
    return cl + cr + c
N = int(input())
A = list(map(int, input().split()))
print(count(A, 0, N-1))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-


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


def mergeSort(lst, left, right):
    if left + 1 < right:
        mid = (left + right) >> 1
        cnt = mergeSort(lst, left, mid)
        cnt += mergeSort(lst, mid, right)
        return merge(lst, left, mid, right) + cnt
    else:
        return 0


def inversions(lst, n):
    return mergeSort(lst, 0, n)


def countingSort(lst, n):
    cnt_lst = [0] * (max(lst)+1)

    for i in range(0, n):
        cnt_lst[lst[i]] += 1

    i = 0
    result = []
    for j, cnt in enumerate(cnt_lst):
        for _ in range(0, cnt):
            result.append(j)
    return result


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    print(inversions(lst, n))

Submission status: Accepted

Solution code:

def merge(A,left,mid,right):
    '''n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(0,n1):
        L.append(A[left+i])
 
    for i in range(0,n2):
        R.append(A[mid+i])
    L.append(1000000001)
    R.append(1000000001)
    '''
    L = A[left:mid]+[1000000001]
    R = A[mid:right]+[1000000001]
 
    i = 0
    j = 0
    cnt = 0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k]=L[i]
            i += 1
        else:
            if L[i] < 1000000001:
                cnt += mid-left -i
            A[k] = R[j]
            j += 1
    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
 
 
if __name__ == '__main__':
    n = (int)(input())
    a = list(map(int,input().split()))
     
    cnt = mergeSort(a,0,n)
#    print(*a)
    print(cnt)

Submission status: Accepted

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

def merge_and_count(a, b):
    i, j = 0, 0
    count = 0
    m = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            m.append(a[i])
            i += 1
        else:
            count += len(a)-i
            m.append(b[j])
            j += 1

    if i < len(a):
        m += a[i:]
    else:
        m += b[j:]

    return (count, m)



def sort_and_count(l):
    if len(l) == 1:
        return 0, l
    else:
        a = l[0:len(l)//2]
        b = l[len(l)//2:]
        rA, a_ = sort_and_count(a)
        rB, b_ = sort_and_count(b)
        r, l_ = merge_and_count(a_, b_)
    return (rA+rB+r, l_)

print(sort_and_count(a)[0])

Submission status: Accepted

Solution code:
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = j = 0
    limit = mid - left
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            if i >= limit:
                A[k + 1: right] = R[j: -1]
                break
        else:
            cnt += limit - 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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = j = 0
    limit = mid - left
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            cnt += limit - 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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            cnt += j
            i += 1
        else:
            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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    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:
            A[k] = R[j]
            cnt += n1 - i
            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)
    

if __name__ == '__main__':

    n = int(input())
    A = [int(a) for a in input().split(" ")]
    cnt = 0
    mergeSort(A, 0, n)
    print(cnt)

Submission status: Accepted

Solution code:
count = 0

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

    l = a[left:mid]
    r = a[mid:right]
    l.append(10**9+1)
    r.append(10**9+1)

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


if __name__ == '__main__':
    n = int(input())
    a = [int(x) for x in input().split()]

    mergeSort(a, 0, n)

    print(count)

Submission status: Accepted

Solution code:
INF = 10 ** 10

def merge(hoge, left, mid, right):
    c = 0
    n1 = mid - left
    n2 = right - mid
    Left = [hoge[left+i] for i in range(n1)]
    Right = [hoge[mid+i] for i in range(n2)]
    Left.append(INF)
    Right.append(INF)
    i = 0
    j = 0
    for k in range(left, right):
        if Left[i] <= Right[j]:
            hoge[k] = Left[i]
            i += 1
        else:
            hoge[k] = Right[j]
            j += 1
            c += n1 - i
    return c

def mergeSort(hoge, left, right):
    c = 0
    if left+1 < right:
        mid = (left + right) // 2
        c += mergeSort(hoge, left, mid)
        c += mergeSort(hoge, mid, right)
        c += merge(hoge, left, mid, right)
    return c

if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    print (mergeSort(hoge, 0, len(hoge)))

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1;c+=m-l-i
 return c
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  return s(A,l,m)+s(A,m,r)+g(A,l,m,r)
 else:return 0
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(c)

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(c)

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
if'__main__'==__name__:
 c=0
 n=int(input())
 A=list(map(int,input().split()))
 s(A,0,n)
 print(c)

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
def m():
 n,A=int(input()),list(map(int,input().split()))
 s(A,0,n);print(c)
if'__main__'==__name__:c=0;m()

Submission status: Accepted

Solution code:
# Merge Sortを元に分割統治で反転数を求める
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 = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
# R[j]について，Lに含まれマージ後にR[j]よりも後に移動するような要素の数
            cnt += n1 - i
            A[k] = R[j]
            j += 1

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

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

Submission status: Accepted

Solution code:
def count(nums):
    """count the number of inversions (ai > aj and i < j)
    in a sequence of ints num.

    >>> count([3, 5, 2, 1, 4])
    6
    >>> count([10, 2, 9, 4, 6, 5, 7, 8, 3, 1])
    29
    """
    def _count(i, j):
        if i < j:
            mid = (i + j) // 2
            i1, li1 = _count(i, mid)
            i2, li2 = _count(mid+1, j)

            return _merge(li1, li2, i1 + i2)
        else:
            return (0, nums[i:i+1])

    def _merge(li1, li2, invs):
        i = j = 0
        result = []
        sums = inv = 0
        while i < len(li1) and j < len(li2):
            if li1[i] > li2[j]:
                result.append(li2[j])
                inv += 1
                j += 1
            else:
                result.append(li1[i])
                invs += sums + inv
                sums += inv
                inv = 0
                i += 1

        while i < len(li1):
            result.append(li1[i])
            invs += sums + inv
            sums += inv
            inv = 0
            i += 1
        if j < len(li2):
            result.extend(li2[j:])

        return (invs, result)

    invs, _ = _count(0, len(nums))
    return invs

def run():
    _ = int(input())  # flake8: noqa
    nums = [int(i) for i in input().split()]

    print(count(nums))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1]
    r = a[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    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]
            c += n1 - i
            j += 1

def mergeSort(a, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right) / 2)
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

n = int(input())
a = list(map(int,input().split()))
c = 0
mergeSort(a, 0, n)
print(c)

Submission status: Accepted

Solution code:
n = int(input())
lis = list(map(int,input().split()))
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    global ans
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1
            ans += (len(left) - l_i)

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

ans = 0
merge_sort(lis)
print(ans)

Submission status: Accepted

Solution code:
#教室内の位置は右*中央
#問題は「Recursion / Divide and Conquer - The Number of Inversions」(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp)

#とりあえず入力部
n = int(input())
lis = list(map(int,input().split()))

#方針ですが、N=200000というところから、O(N)もしくはO(NlogN)であるという推測が立ちます。
#転倒数はバブルソートの時の入れ替えの回数というヒントが示されているので、ソートを使えばいいのではないかという予想が生えます
#というわけで計算量が一定であるところのマージソートが良さそうという気がします
#マージソートの機構を考えれば、マージの際に左側と右側を合わせていくわけですが、
#左側の数字が右の数字より大きい場合、その分だけ転倒数が生まれます(それぞれは部分的にソートされているので)
#したがって、マージする時に左が右より大きければある数だけ転倒数を増やします
#「ある数」とは、左側にあとn個数字が残っていればそのタイミングでのnになります
#以下は実装部分ですが、マージソートを描くのが面倒なのでQiitaから貼り付けました
#マージの部分が関数になっているので、ansを増やす時に関数の中で動かすためグローバル変数にします

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


def merge(left, right):
    global ans
    merged = []
    l_i, r_i = 0, 0

    while l_i < len(left) and r_i < len(right):
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1
            ans += (len(left) - l_i)

    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

ans = 0
merge_sort(lis)
print(ans)

Submission status: Accepted

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    h=[]
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            h.append(L[i])
            i += 1
        else:
            A[k] = R[j]
            h.append(R[j])
            j += 1
            if i < len(L)-1:
                count += len(L) - 1 - i
        
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

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

Submission status: Accepted

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    h=[]
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            h.append(L[i])
            i += 1
        else:
            A[k] = R[j]
            h.append(R[j])
            j += 1
            if i < len(L)-1:
                count += len(L) - 1 - i
        
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

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

Submission status: Accepted

Solution code:
#16D8103010K Ko Okasaki
#ALDS_5_D

global cnt
cnt=0

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

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)

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

mergeSort(S,0,n)
print(cnt)

Submission status: Accepted

Solution code:
global cnt
cnt=0

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

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)

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

mergeSort(S,0,n)
print(cnt)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    count = 0
    L = A[left: mid]
    R = A[mid: right]
    L.append(10e9 + 1)
    R.append(10e9 + 1)
    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 += (len(L)-1) - i
    return count

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = int((left + right)/2)
        v1 = merge_sort(A, left, mid)
        v2 = merge_sort(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(' ')))

ans = merge_sort(A, 0, n)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
cnt = 0
SENTINEL = 10e9 + 1
def merge(a, left, mid, right):
    global cnt
    l = a[left: mid] + [SENTINEL]
    r = a[mid: right] + [SENTINEL]
    n1 = mid - left
    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]
            cnt += n1 - i
            j += 1

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

merge_sort(s, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
global cnt
cnt = 0

def merge(A, left, mid, right):
    L = A[left:mid] + [float("inf")]
    R = A[mid:right] + [float("inf")]

    i = 0
    j = 0
    global cnt
    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] != float("inf"):
                cnt += len(L)-1-i

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

    return rsl


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

mergesort(S, 0, n)
print(cnt)

Submission status: Accepted

Solution code:

def merge(a, left, mid, right):
    x = 0
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("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
            x += mid - (left+i)
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(x[0])

Submission status: Accepted

Solution code:
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1]
    r = a[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    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]
            c += n1 - i
            j += 1
 
def mergeSort(a, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right) / 2)
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)
 
n = int(input())
a = list(map(int,input().split()))
c = 0
mergeSort(a, 0, n)
print(c)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
count = 0
 
def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 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 += len(l) - i - 1
def mergeSort(a, left, right):
    if left + 1 < right:
        mid = right + (left - right)//2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)
 
mergeSort(s, 0, n) 
print(count)