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

def merge(A,left,mid,right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000000)
    R.append(1000000000)

    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]
            count += len(L) - i - 1
            j += 1

n = int(input())
nums = list(map(int,input().split(" ")))
count = 0

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
import sys
if sys.version_info[0]>=3: raw_input=input

def M(l,r):
	if l+1>=r: return 0
	if l+2==r:
		if A[l]<=A[l+1]: return 0
		A[l],A[l+1]=A[l+1],A[l]
		return 1
	m = (l+r)//2
	i=l
	j=m
	k=l
	cl=M(l,m)
	cr=M(m,r)
	c=0
	while i<m and j<r:
		if A[i]<=A[j]:
			W[k]=A[i]
			k+=1
			i+=1
		else:
			W[k]=A[j]
			k+=1
			j+=1
			c+=m-i
	while i<m:
		W[k]=A[i]
		k+=1
		i+=1
	while j<r:
		W[k]=A[j]
		k+=1
		j+=1
	for i in range(l,r): A[i]=W[i]
	return cl+cr+c

raw_input()
A=list(map(int,raw_input().split()))
W=[0]*len(A)
print(M(0,len(A)))

Submission status: Accepted

Solution code:
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)
b=[0]*(1+r)
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<=r:
        b[n]+=1
        n+=n&-n
print s

Submission status: Accepted

Solution code:
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Submission status: Accepted

Solution code:
SENTINEL = 10 ** 9 +1
cnt = 0
def merge(A, left, mid, right):
    global cnt

    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    
    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
            cnt += 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)

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

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    global cnt
    l = a[left:mid] + [sentinel]
    r = a[mid:right] + [sentinel]
    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
            cnt += 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)

n = input()
a = list(map(int, input().split()))
sentinel = 10 ** 9 + 1
cnt = 0
merge_sort(a, 0, len(a))
print(cnt)

Submission status: Accepted

Solution code:
import sys
count = 0
def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxint)
    R.append(sys.maxint)
    i = 0
    j = 0
    t = 0
    for k in xrange(left, right):
        if L[i] <= R[j]:
            count += t
            A[k] = L[i]
            i += 1
        else:
            t += 1
            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(raw_input())
A = map(int, raw_input().split())
mergeSort(A, 0, n)
print count

Submission status: Accepted

Solution code:
#global count
#count = 0

def marge(A,left,mid,right):
    #    global count
    n1 = mid -left
    n2 = right -mid
    L = []
    R = []
    for i in range(left,n1+left):
        L.append(A[i])
    for i in range(mid,n2+mid):
        R.append(A[i])

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

    return cnt

def margeSort(A,left,right):
    if left+1 < right:
        mid = int((left+right)/2)
        c1 = margeSort(A,left,mid)
        c2 = margeSort(A,mid,right)
        c3 = marge(A,left,mid,right)
        return c1+c2+c3
    else:
        return 0

n = int(input())
st = input()
A = list(map(int,st.split()))
ans = margeSort(A,0,n)

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_D

def merge(array, left, mid, right):
    global cnt
    L = array[left:mid]  + [sentinel]
    R = array[mid:right] + [sentinel]
    i = j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
            cnt += len(L) - 1 - i

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

n = int(input())
numbers = list(map(int, input().split()))
cnt = 0
sentinel = 10 ** 9 + 1
merge_sort(numbers, 0, len(numbers))
print(cnt)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_D

def merge(array, left, mid, right):
    global cnt
    L = array[left:mid]  + [SENTINEL]
    R = array[mid:right] + [SENTINEL]
    i = j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
            cnt += len(L) - 1 - i

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

n = int(input())
numbers = list(map(int, input().split()))
cnt = 0
SENTINEL = 10 ** 9 + 1
merge_sort(numbers, 0, len(numbers))
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    for k in range(l, r):
        if not rl or ll and ll[0] < rl[0]:
            a[k] = ll.popleft()
        else:
            a[k] = rl.popleft()
            cnt += len(ll)


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


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

Submission status: Accepted

Solution code:
sentinel = 1000000001

def merge(A, left, mid, right):
    """Merge the two sorted partial sequences A[left:mid] and A[mid:right].

    To count the number of inversions,
    make a global declaration for the variable cnt.
    """
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    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
            cnt += (n1 - 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)


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

cnt = 0

mergeSort(S, 0, n)

print(cnt)

Submission status: Accepted

Solution code:
sentinel = 1000000001

def merge(A, left, mid, right):
    """Merge the two sorted partial sequences A[left:mid] and A[mid:right].

    To count the number of inversions,
    make a global declaration for the variable cnt.
    """
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    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
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0


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

cnt = 0

n_ivs =  mergeSort(S, 0, n)

print(n_ivs)

Submission status: Accepted

Solution code:
sentinel = 1000000001

def merge(A, left, mid, right):
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    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
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0


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

cnt = 0

n_ivs =  mergeSort(S, 0, n)

print(n_ivs)

Submission status: Accepted

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

def merge(A, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1) 
    R = [0] * (n2+1)
    L[:n1] = A[left:mid]
    R[:n2] = A[mid:right]
    #for i in xrange(n1):
    #    L[i] = A[left + i]
    #for i in xrange(n2):
    #    R[i] = A[mid + i]
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    for k in xrange(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 right - left > 1:
        mid = int((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

def main():
    v = mergeSort(S, 0, len(S))
    print v
    return 0

main()

Submission status: Accepted

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


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

cnt = 0
input()
num = list(map(int, input().split()))
merge_count(num, 0, len(num))
print(cnt)

Submission status: Accepted

Solution code:
def merge(A,left,mid,right):
    global ct
    n1=mid-left
    n2=right-mid
    l=[A[left+i] for i in xrange(n1)]
    r=[A[mid+i] for i in xrange(n2)]
    l.append(float('inf'))
    r.append(float('inf'))
    i=0
    j=0
    for k in xrange(left,right):
        if l[i]<=r[j]:
            A[k]=l[i]
            i=i+1
        else:
            A[k]=r[j]
            j=j+1
            ct+=n1-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)

ct=0
n=input()
A=map(int,raw_input().split())
mergesort(A,0,n)
print(ct)

Submission status: Accepted

Solution code:
import sys

cnt = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = range(n1 + 1)
    R = range(n2 + 1)

    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    L[n1] = 1000000000
    R[n2] = 1000000000
    i = 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
            cnt += n1 - 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__":
    lines = sys.stdin.readlines()
    S = map(int, lines[1].split())
    mergeSort(S, 0, int(lines[0]))
    print cnt

Submission status: Accepted

Solution code:
from array import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array('I', [])  # List is too slow. Use an array instead.
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += len(left[lpos:])
            rcount += len_left - lpos
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global count
    banpei = 1000000001
    L = A[left:mid]
    l = len(L)
    L += [banpei]
    R = A[mid:right] + [banpei]

    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 += l - i
    return count


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

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

Submission status: Accepted

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

import sys

def merge(A, left, mid, right):
    global count
    n1 = mid-left
    n2 = right-mid
    L = [0]*(n1+1)
    R = [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] = R[n2] = sys.maxint
    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 += n1-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)

n = int(raw_input())
S = map(int, raw_input().split())
count = 0
mergeSort(S, 0, n)
print count

Submission status: Accepted

Solution code:
cnt = 0
def merge(L,R):
    global cnt
    n = len(L)+len(R)
    lenL = len(L)
    A = []
    i = j = 0
    L.append(10**9+1)
    R.append(10**9+1)
    for _ in range(n):
        if L[i] <= R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
            cnt += lenL-i
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 

if __name__=='__main__':
    n = int(input()) 
    mergeSort(list(map(int,input().split())))
    print(cnt)

Submission status: Accepted

Solution code:
def invNum(d,A):
    if d < 0 or len(A) < 2: return 0
    cnt = 0
    L = []
    R = []
    for ai in A:
        if ai < 2**d:
            L.append(ai)
            cnt += len(R)
        else:
            R.append(ai-2**d)
    return cnt + invNum(d-1,L) + invNum(d-1,R)
 
if __name__=='__main__':
    n = int(input()) 
    print(invNum(29,list(map(int,input().split()))))

Submission status: Accepted

Solution code:
cnt = 0
def merge(L,R):
    global cnt
    n = len(L)+len(R)
    lenL = len(L)
    A = []
    i = j = 0
    L.append(-1)
    R.append(-1)
    for _ in range(n):
        if L[i] > R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
            cnt += lenL-i
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 

if __name__=='__main__':
    n = int(input()) 
    A = list(map(int,input().split()))
    mergeSort(A[::-1])
    print(cnt)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    global cnt
    l = a[left:mid] + [10**9 + 1]
    r = a[mid:right] + [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:
            cnt += len(l) - 1 - i  # rest of left-[10**9+1]
            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())
a = list(map(int, input().split()))
cnt = 0
mergesort(a, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
def merge(targ,first,mid,last):
    left = targ[first:mid] + [10 ** 9 + 1]
    right = targ[mid:last] + [10 ** 9 + 1]

    leftcnt = rightcnt = 0
    global ans
    for i in range(first,last):
        #print(left,right,left[leftcnt],right[rightcnt],targ,ans)
        if left[leftcnt] <= right[rightcnt]:
            targ[i] = left[leftcnt]
            leftcnt += 1
        else:
            ans += len(left)-1-leftcnt
            targ[i] = right[rightcnt]
            rightcnt += 1

def mergesort(targ,first,last):
    if first + 1 == last:
        if targ[first] > targ[last]:
            #print(targ[first] , targ[last])
            global ans
            temp = targ[first]
            targ[first] = targ[last]
            targ[last] = temp
            ans += 1

    elif first == last:
        pass
    else:
        mid = (first + last) // 2
        mergesort(targ,first,mid)
        mergesort(targ,mid,last)
        merge(targ,first,mid,last)


ans = 0
num = int(input())
targ = [int(n) for n in input().split(' ')]
mergesort(targ,0,num-1)
print(ans)

Submission status: Accepted

Solution code:
import sys

sintinel = 1000000001

def merge_sort(A, l, r):
    if l + 1 < r:
        mid = (l + r) // 2
        cnt1 = merge_sort(A, l, mid)
        cnt2 = merge_sort(A, mid, r)
        cnt3 = merge(A, l, mid, r)
        return (cnt1 + cnt2 + cnt3)
    else:
        return 0

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

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

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

Submission status: Accepted

Solution code:
def bubble_sort_revision(target_list):#?????????????????????

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    
    for top_index in range(1,list_length):
        for i in range(top_index, list_length)[::-1]:
            if target_list[i] < target_list[i - 1] and target_list[top_index] >= target_list[i]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                
    return change_count

def my_add(bit, i, x):
    while i <= len(bit) - 1:
        bit[i] += x
        i += int(bin(i & -i), 2)
        
def my_sum(bit, i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= int(bin(i & -i), 2)
    return s

def merge(l,r):
    global count
    l_index = 0
    r_index = 0
    merge_list = []
    l.append(pow(10,9) + 1)
    r.append(pow(10,9) + 1)

    len_l = len(l) - 1
    for k in range(len(l) + len(r) - 2):
        if l[l_index] < r[r_index]:
            merge_list.append(l[l_index])
            l_index += 1
            len_l -= 1
        else:
            count += len_l
            merge_list.append(r[r_index])
            r_index += 1

    return merge_list
    
def merge_sort(target_list):
    if len(target_list) == 1:
        return target_list
    
    mid = int(len(target_list) / 2)
    
    r = merge_sort(target_list[mid:])
    l = merge_sort(target_list[:mid])
    
    return merge(l, r)

def bit_solve(n, target_list):#???????????§????????????bit?????§?????????????????????
    bit = [0 for i in range(max(target_list) + 2)]
    ans = 0
    for i in range(n):
        ans += i - my_sum(bit, target_list[i] + 1)
        my_add(bit, target_list[i] + 1, 1)
        print(ans, target_list[i], bit)
    return ans

if __name__ == "__main__":
    global count
    count = 0
    l = int(input())
    target_list = [int(i) for i in input().split()]
    merge_sort(target_list)
    print(count)

Submission status: Accepted

Solution code:
 #coding:UTF-8
def Marge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[]
    R=[]
    c=0
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(100000000000000000)
    R.append(100000000000000000)
    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
            c+=n1-i
    return c
            
def MS(A,left,right,c):
    
    if left+1<right:
        mid=int((left+right)/2)
        c1=MS(A,left,mid,c)
        c2=MS(A,mid,right,c)
        c3=Marge(A,left,mid,right)
        return c1+c2+c3
    return 0
 
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    cnt=0
    for i in range(n):
        A[i]=int(A[i])
    cnt=MS(A,0,n,0)
    print(cnt)

Submission status: Accepted

Solution code:

def merge(ns, ns1, ns2, n, mid):
    j = 0
    k = 0
    c = 0
    for i in range(n):
        if ns1[j] < ns2[k]:
            ns[i] = ns1[j]
            j += 1
            if j == mid:
                for l in range(n - mid - k):
                    ns[i + 1 + l] = ns2[k + l]
                return c
        else:
            ns[i] = ns2[k]
            k += 1
            c += mid - j
            if k == n - mid:
                for l in range(mid - j):
                    ns[i + 1 + l] = ns1[j + l]
                return c

def merge_sort(ns, n):
    if n <= 1:
        return 0
    elif n == 2:
        if ns[0] > ns[1]:
            k = ns[0]
            ns[0] = ns[1]
            ns[1] = k
            return 1
        else:
            return 0
    else:
        mid = n // 2
        ns1 = ns[:mid]
        ns2 = ns[mid:]
        c1 = merge_sort(ns1, mid)
        c2 = merge_sort(ns2, n - mid)
        c3 = merge(ns, ns1, ns2, n, mid)
        return c1 + c2 + c3

def compute_inversions(ns, n):
    return merge_sort(ns, n)

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

print(compute_inversions(ns, n))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def merge(_array, left, mid, right):
    count = 0
    array_left = _array[left:mid] + [1e9 + 1]
    array_right = _array[mid:right] + [1e9 + 1]
    left_length, right_length = mid - left, right - mid

    i, j = 0, 0

    for k in range(left, right):
        if array_left[i] <= array_right[j]:
            _array[k] = array_left[i]
            i += 1
        else:
            _array[k] = array_right[j]
            j += 1
            count += left_length - i
    return count


def merge_sort(_array, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        c1 = merge_sort(_array, left, mid)
        c2 = merge_sort(_array, mid, right)
        c3 = merge(_array, left, mid, right)
        return c1 + c2 + c3
    else:
        return 0


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # count = 0

    ans = merge_sort(array, 0, array_length)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def mergeSort(A,left,right):

    middle = (left + right) // 2
    if left + 1 < right:
        mergeSort(A, left, middle)
        mergeSort(A, middle, right)
        merge(A,left,right,middle)
    
def merge(A,left,right,middle):
    global count
        
    L = deque(A[left:middle])
    R = deque(A[middle:right])
    L.append(float("inf"))
    R.append(float("inf"))
    for i in range(left,right):
        
        if L[0] < R[0]:
            A[i] = L.popleft()
        else:
            A[i] = R.popleft()
            count += len(L) -1 
count = 0     
input()
A = list(map(int,input().split()))
mergeSort(A,0,len(A))
print(count)

Submission status: Accepted

Solution code:
from _collections import deque

SENIAL = 1000000000
def mergeSort(A,left,right):
    if left + 1 < right:
        middle = (left + right) // 2
        mergeSort(A, left, middle)
        mergeSort(A, middle, right)
        merge(A,left,right,middle)
    
def merge(A,left,right,middle):
    global count        
    L = deque(A[left:middle])
    R = deque(A[middle:right])
    L.append(SENIAL)
    R.append(SENIAL)
    for i in range(left,right):
        if L[0] < R[0]:
            A[i] = L.popleft()
        else:
            A[i] = R.popleft()
            count += len(L) -1 
count = 0     
input()
A = list(map(int,input().split()))
mergeSort(A,0,len(A))
print(count)

Submission status: Accepted

Solution code:
SENTINEL = 1000000001

def merge(A, l, m, r):
  L = A[l:m] + [SENTINEL]
  R = A[m:r] + [SENTINEL]
  i = 0
  j = 0
  cnt = 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
      cnt += len(L) - 1 - i
  return cnt

def merge_sort(A, l, r):
  if l + 1 < r:
    m = (l + r) // 2
    cnt = 0
    cnt += merge_sort(A, l, m)
    cnt += merge_sort(A, m, r)
    cnt += merge(A, l, m, r)
    return cnt
  else:
    return 0

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

print(merge_sort(A, 0, n))

Submission status: Accepted

Solution code:
import sys

a_max = 10000000000

def merge_sort(A):
	n = len(A)
	num_swap = 0

	if n > 1:
		m = n // 2
		num_swap0, A0 = merge_sort(A[0:m])
		num_swap1, A1 = merge_sort(A[m:])
		
		num_swap += num_swap0 + num_swap1

		n1 = len(A0)
		A0.append(a_max)
		A1.append(a_max)	
		i = 0
		j = 0		
		
		for k in range(n):
			if A0[i] < A1[j]:
				A[k] = A0[i]

				i += 1
			else:
				A[k] = A1[j]

				num_swap += n1 - i
				j += 1

	return num_swap, A

def bubble_sort(A):
	n = len(A)
	num_swap = 0

	for i in range(n):
		for j in range(n - 1, i, -1):
			if A[j] < A[j - 1]:
				A[j], A[j - 1] = A[j - 1], A[j]
				num_swap += 1

	return num_swap, A

#fin = open("test.txt", "r")
fin = sys.stdin

fin.readline()
A = list(map(int, fin.readline().split()))

num_swap, B = merge_sort(A)
#num_swap, B = bubble_sort(A)

print(num_swap)
#print(B)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    l = len(L)
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt += l-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)
    else:
        return 0

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

Submission status: Accepted

Solution code:
count = 0

def merge(A, left, mid, right):
  global count
  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
  numLeft = len(L)-1 # the number of L's elements
  for k in range(left, right):
    if R[j] < L[i]:
      A[k] = R[j]
      j += 1
      count += numLeft-i # the number of inversions to R[j]
    else:
      A[k] = L[i]
      i += 1

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)


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

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global cnt
    L = A[left:mid] + [1000000001]
    R = A[mid:right] + [1000000001]
    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())
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)
print(str(cnt))