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
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
cnt = 0
inf = float('inf')

def merge_sort(left, right):
    if right-left > 1:
        middle = (left+right) // 2
        merge_sort(left, middle)
        merge_sort(middle, right)
        merge(left, middle, right)

def merge(left, middle, right):
    left_part = A[left:middle]
    right_part = A[middle:right]
    left_part.append(inf)
    right_part.append(inf)
    l, r = 0, 0
    global cnt
    left_size = middle-left
    for i in range(left, right):
        if left_part[l] < right_part[r]:
            A[i] = left_part[l]
            l += 1
        else:
            A[i] = right_part[r]
            cnt += max(left_size-l, 0)
            r += 1

def main():
    merge_sort(0, n)
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 0～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret




N = int(input())

a = list(map(int,input().split()))
b = a.copy()
b.sort()
dic = {}

for i in range(N):
    dic[b[i]] = i+1

for i in range(N):
    a[i] = dic[a[i]]

BIT = [0] * (N+1)
ans = 0
a.reverse()

for i in range(N):

    ans += bitsum(a[i],BIT)
    bitadd(a[i],1,BIT)
    #print (BIT,ans)

print (ans)

Submission status: Accepted

Solution code:
cnt = 0
def count(A, left, mid, right):
    L = []
    R = []
    for l in A[left:mid]:
        L.append(l)
    for r in A[mid:right]:
        R.append(r)
    global cnt
    l_idx = 0
    r_idx = 0
    cnt_part = 0
    for i in range(left, right):
        if l_idx >= len(L):
            A[i] = R[r_idx]
            r_idx += 1
            continue
        if r_idx >= len(R):
            A[i] = L[l_idx]
            l_idx += 1
            if l_idx < len(L):
                cnt_part += r_idx
            continue
        if L[l_idx] > R[r_idx]:
            A[i] = R[r_idx]
            cnt_part += 1
            r_idx += 1
        else:
            A[i] = L[l_idx]
            l_idx += 1
            if l_idx < len(L):
                cnt_part += r_idx
    cnt += cnt_part
def count_inversion_number(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        count_inversion_number(A, left, mid)
        count_inversion_number(A, mid, right)
        count(A, left, mid, right)
n = int(input())
A = list(map(int, input().split(' ')))
count_inversion_number(A, 0, n)
print(cnt)

Submission status: Accepted

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

    i = 0
    j = 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
            count += (n1 -i)

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

n = int(input())
count = 0
s = list(map(int, input().split()))
mergesort(s, 0, n)
print(count)

Submission status: Accepted

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

def mergeSort(A,left,right):
    global cnt

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

    inf = float('inf')
    L = A[left:mid]+[inf]
    R = A[mid:right] + [inf]
    cnt = 0
    n1 = len(L)-1
    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 += n1-i
    return cnt


def mergeSort(A, left, right, count = 0):
    if left+1 < right:
        mid = (left + right)//2
        cnt1 = mergeSort(A, left, mid, count)
        cnt2 = mergeSort(A, mid, right, count)
        cnt3 = merge(A, left, mid, right)
        return cnt1+cnt2+cnt3
    else:
        return 0
n  = int(input())
A = list(map(int, input().split()))
ans = mergeSort(A, 0, n)

print(ans)

Submission status: Accepted

Solution code:
count = 0

def merge(a, left, mid, right):
    global count
    L = [0] * (mid - left + 1)
    R = [0] * (right - mid + 1)

    for i in range(len(L)):
        if i  == len(L) - 1:
            L[i] = float('inf')
        else:
            L[i] = a[left+i]
    
    for i in range(len(R)):
        if i == len(R) - 1:
            R[i] = float('inf')
        else:
            R[i] = a[mid+i]

    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            if i != len(L) - 1 and j != len(R) - 1:
                count += len(L) - i - 1
            a[k] = R[j]
            j += 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)

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

mergeSort(a, 0, l)
print(count)

Submission status: Accepted

Solution code:
cnt = 0

def merge(a, b):
    global cnt
    c = []
    i = 0
    j = 0
    for k in range(len(a)+len(b)):
        if i < len(a) and j < len(b) and a[i] > b[j]:
            c.append(b[j])
            cnt = cnt + len(a) - i
            j = j + 1
        elif i >= len(a):
            c.append(b[j])
            j = j + 1
        else:
            c.append(a[i])
            i = i + 1
    return c

def mergesort(a):
    if len(a) == 1:
        return a
    else:
        return merge(mergesort(a[:len(a)//2]), mergesort(a[len(a)//2:]))

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

mergesort(a)

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

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

c = 0

def merge(A, left, mid, right):
  inf = float('inf')
  L = A[left:mid] + [inf]
  R = A[mid:right] + [inf]
  i = 0
  j = 0
  global c
  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 += 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)

mergesort(S, 0, n)

print(c)

Submission status: Accepted

Solution code:
# ALDS1_5_D

class mergeSort:
    def __init__(self, a):
        self.a = a

    def mergeSort(self, left, right):
        if left + 1 < right: # rightはリストの末尾 +1
            middle = (left + right) // 2
            v1 = self.mergeSort(left, middle)
            v2 = self.mergeSort(middle, right)
            v3 = self.merge(left, middle, right)
            return v1 + v2 + v3
        else:
            return 0
    
    def merge(self, left, mid, right):
        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"))
        p = 0 # l's
        q = 0 # r's
        cnt = 0
        for k in range(left, right):
            if l[p] > r[q]: # 反転することになる
                self.a[k] = r[q]
                if l[p] != float("inf"):
                    cnt += (mid - left) - p
                q += 1
            else:
                self.a[k] = l[p]
                p += 1
        return cnt

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

Submission status: Accepted

Solution code:
import math
import sys

_num_inversions = 0

def merge_sort(A, left, right):
    """数列 A を in place に昇順にソートする。

    left は A の先頭のインデックス、right は末尾のインデックスのひとつ後ろ。
    """
    if left + 1 < right:
        mid = (left  + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

def merge(A, left, mid, right):
    """ソート済みの部分列をマージする。

    数列 A の left から mid - 1 の要素、mid から right - 1 までの
    ２つの部分列はソート済みである。これをマージして、left から right - 1 まで
    ソートする。
    """
    first = A[left:mid]
    first.append(math.inf)  # 番兵
    second = A[mid:right]
    second.append(math.inf) # 番兵

    global _num_inversions
    i = j = 0
    for k in range(left, right):
        if first[i] <= second[j]:
            A[k] = first[i]
            i += 1
        else:
            A[k] = second[j]
            j += 1
            _num_inversions += len(first) - i - 1


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))

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

Submission status: Accepted

Solution code:
class BIT():
    def __init__(self,n):
        self.dat = [0]*(n+1)

    def add(self,a,x):
        i = a
        while i < len(self.dat):
            self.dat[i] = self.dat[i] + x
            i += i & -i

    def sum(self,a):
        res = 0
        i = a
        while i > 0:
            res += self.dat[i]
            i -= i & -i
        return res

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
tmp = BIT(n)
dic = {}
for i in range(len(b)):
    dic[b[i]] = i+1

ans = 0
for j in range(n):
    ans += j - tmp.sum(dic[a[j]])
    tmp.add(dic[a[j]],1)
print(ans)

Submission status: Accepted

Solution code:
count = 0


def merge_sort(n, nums):
    global count
    if n == 1:
        return nums
    left_n = n // 2  # 左側が小さい
    left_sorted = merge_sort(left_n, nums[:left_n]) + [10**9 + 1]  # 番兵
    right_n = n - left_n
    right_sorted = merge_sort(right_n, nums[left_n:]) + [10**9 + 1]  # 番兵
    left_idx = 0
    right_idx = 0
    idx = 0
    sorted_list = [0] * n
    while idx < n:
        if left_sorted[left_idx] <= right_sorted[right_idx]:
            sorted_list[idx] = left_sorted[left_idx]
            left_idx += 1
        else:
            sorted_list[idx] = right_sorted[right_idx]  # 反転したとき
            if left_sorted[left_idx] <= 10**9 and right_sorted[right_idx] <= 10**9:
                count += left_n - left_idx
            right_idx += 1
        idx += 1
    return sorted_list


def main():
    n = int(input())
    nums = list(map(int, input().split(" ")))
    merge_sort(n, nums)
    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = int(1e18)

def merge(A, left, mid, right):
    L = A[left:mid]
    n1 = len(L)
    R = A[mid:right]
    L.append(INF)
    R.append(INF)
    i, j, count = 0, 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
            # Lで超える分がひっくり返す回数 (?)
            count += n1 - i
    return count

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

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

Submission status: Accepted

Solution code:
#A
N = int(input())
A = list(map(int,input().split()))
B = []
for i,a in enumerate(A):
    B.append([a,i])
B.sort()
A = [0]*N
for i in range(N):
    bind = B[i][1]
    A[i] = bind+1
    

#BIT(1-indexed)
BIT = [0]*(N+1)
def BIT_SUM(i):
    s = 0
    while i > 0:
        s+=BIT[i]
        i-=i&(-i)
    return s
def BIT_ADD(i,x):
    while i <= N:
        BIT[i]+=x
        i+=i&(-i)
        
ans = 0
for j in range(N):
    ans+=j-BIT_SUM(A[j])
    BIT_ADD(A[j],1)
print(ans)

Submission status: Accepted

Solution code:


def merge(A, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])
    L.append(2000000000)
    R.append(2000000000)
    
    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
            cnt += n1 - i
    return cnt

def mergeSort(A, left, right):
    if left + 1 < right:
        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
        
        

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

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    NL = len(L)
    NR = len(R)
    i = 0
    j = 0
    ret = 0
    for k in range(left, right):
        if i == NL:
            A[k] = R[j]
            j += 1
        elif j == NR:
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            ret += NL - i
    return ret


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


def main():
    N, *S = map(int, open(0).read().split())
    ret = mergesort(S, 0, len(S))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def merge(numlist, left, mid, right):
    L = numlist[left:mid] + [sys.maxsize]
    R = numlist[mid:right] + [sys.maxsize]
    i = j = 0
    k = left
    inv = 0
    while k < right:
        if L[i] < R[j]:
            numlist[k] = L[i]
            i += 1
        else:
            inv += (mid - left - i)
            numlist[k] = R[j]
            j += 1
        k += 1
    return inv


def cal_inv(numlist, left, right):
    if right > left + 1:
        mid = (left + right) // 2
        linv = cal_inv(numlist, left, mid)
        rinv = cal_inv(numlist, mid, right)
        return linv + rinv + merge(numlist, left, mid, right)
    else:
        return 0
    

if __name__ == '__main__':
    n  = int(input())
    numlist = [int(num) for num in input().split(' ')]
    print(cal_inv(numlist, 0, n))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

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

def InversionNumber(lst):
    bit=BitSum(max(lst))
    res=0
    for i,a in enumerate(lst):
        res+=i-bit.sum(a)
        bit.update(a,1)
    return res

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    s=set()
    for a in aa:
        s.add(a)
    atob={}
    for i,a in enumerate(sorted(s)):
        atob[a]=i+1
    bb=[]
    for a in aa:
        bb.append(atob[a])
    #print(bb)
    print(InversionNumber(bb))

main()

Submission status: Accepted

Solution code:
# alds1_5_d
INF = 1e11

def merge(A, left, mid, right):
    n_inv = 0
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    len_L = len(L) - 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
            n_inv += len_L - i
    return n_inv


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

if __name__ == "__main__":
    n = int(input())
    A = [int(i) for i in input().split()]
    print(merge_sort(A, 0, n))

Submission status: Accepted

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def compress(A):
    """ 座標圧縮 """

    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(set(A))):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

N = INT()
A = LIST()

zipped, _ = compress(A)
bit = BIT(N)
ans = 0
for i in range(N-1, -1, -1):
    a = zipped[A[i]]
    ans += bit.sum(a)
    bit.add(a, 1)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]

def merge(A,l,m,r):
    global c
    L=A[l:m]+[1e10]
    R=A[m:r]+[1e10]
    i,j = 0,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 mergesort(A,l,r):
    if l+1<r:
        m=(r+l)//2
        mergesort(A,l,m)
        mergesort(A,m,r)
        merge(A,l,m,r)
c=0
mergesort(a,0,n)
print(c)

Submission status: Accepted

Solution code:
cnt=0
def merge_sort(S):
    l=len(S)
    mid=int(l/2)
    Left=S[0:mid]
    Right=S[(mid):l]
    global cnt
    if l>=2:
        merge_sort(Left) and merge_sort(Right)
    Left.append(float('inf'))
    Right.append(float('inf'))
    p=0
    q=0
    for i in range(l):
        if Left[p]<Right[q]:
            S[i]=Left[p]
            p+=1
        else:
            S[i]=Right[q]
            q+=1
            if l>1 and len(Left)-1>=p and Left[p]!=float('inf'):
                cnt+=len(Left)-p-1
    return S



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

merge_sort(A)
print(cnt)

Submission status: Accepted

Solution code:
count=0
def merge(A,left,mid,right):
    global count
    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:
            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)

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

Submission status: Accepted

Solution code:
def div(A, l, r):
    if l+1 < r:
        mid = (l+r) // 2
        div(A, l, mid)
        div(A, mid, r)
        solve(A, l, mid, r)

def solve(A, l, m, r):
    global cnt
    l_i = 0
    r_i = 0
    L = A[l:m]
    R = A[m:r]
    L.append(1e9)
    R.append(1e9)
    for i in range(l, r):
        if L[l_i] > R[r_i]:
            A[i] = R[r_i]
            r_i += 1
        else:
            A[i] = L[l_i]
            l_i += 1
            cnt += r_i
n = int(input())
A = list(map(int, input().split()))
cnt = 0
div(A, 0, n)
print(cnt)

Submission status: Accepted

Solution code:
def inv(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);inv(A,l,m,r)
c=0
n=int(input())
A=[int(i) for i in input().rstrip().split(" ")]
s(A,0,n)
print(c)

Submission status: Accepted

Solution code:



def merge(a, left, mid, right):
    L = a[left:mid] + [INF]
    R = a[mid:right] + [INF]
    
       
    i = 0
    j = 0
    for k in range(left, right):
     
        global idx
        
        if( L[i] <= R[j] ):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
            idx += 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)


INF = 1000000000
idx = 0
n = int(input())
a = [int(i) for i in input().split()]
merge_sort(a,0,len(a))
print(idx)

Submission status: Accepted

Solution code:
infinity=2**35
def merge(A,left,mid,right):
  global cnt

  L=A[left:mid]
  R=A[mid:right]
  L.append(infinity)
  R.append(infinity)

  i=0
  j=0

  inver=0

  for k in range(left,right):
    if L[i]<=R[j]:
      A[k]=L[i]
      i+=1
      if inver>0:
        cnt+=inver
      
    else:
      A[k]=R[j]
      j+=1
      inver+=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 main():
    N = int(input())
    A = [int(i) for i in input().split()]
    cnt = 0

    def merge(A, l, mid, r):
        nonlocal cnt
        n1 = mid - l
        n2 = r - mid
        L = [A[l + i] for i in range(n1)]
        R = [A[mid + i] for i in range(n2)]
        L.append(1 << 60)
        R.append(1 << 60)
        i = 0
        j = 0
        for k in range(l, r):
            if L[i] <= R[j]:
                A[k] = L[i]
                i = i + 1
            else:
                cnt += n1 - i
                A[k] = R[j]
                j = j + 1

    def merge_sort(A, left, right):
        if len(A) == 1:
            return
        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(A, 0, N)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
# A=[3,5,2,1,4]
# n=5
# A=[3,1,2]
# n=3
n=int(input())
A=list(map(int,input().split()))
def merge(A,left,mid,right):
    global count
    L=A[left:mid]+[math.inf]
    R=A[mid:right]+[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
            count+=len(L)-1-i
#             print(len(L)-1-i)
#     print("A:",A[left:right])
    
            
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)
count=0
mergeSort(A,0,n)
print(count)

Submission status: Accepted

Solution code:
global count


def merge(arr, l, mid, r):
    arr_copy = list(arr[l:r + 1])
    global count
    l_idx, r_idx = l, mid + 1
    for i in range(l, r + 1):
        if l_idx > mid:
            arr[i] = arr_copy[r_idx - l]
            r_idx += 1
        elif r_idx > r:
            arr[i] = arr_copy[l_idx - l]
            l_idx += 1
        elif arr_copy[l_idx - l] <= arr_copy[r_idx - l]:
            arr[i] = arr_copy[l_idx - l]
            l_idx += 1
        else:
            arr[i] = arr_copy[r_idx - l]
            count += mid - l_idx + 1
            r_idx += 1


def merge_sort(arr, l, r):
    if l >= r:
        return
    mid = (l + r) // 2
    merge_sort(arr, l, mid)
    merge_sort(arr, mid + 1, r)
    merge(arr, l, mid, r)


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    count = 0
    merge_sort(arr, 0, n - 1)
    print(count)

Submission status: Accepted

Solution code:
num = 0
def marge_sort(array):
    global num
    if len(array) < 2: return array
    
    mid = len(array) // 2
    left = marge_sort(array[:mid])
    right = marge_sort(array[mid:])
    
    len_l, len_r = len(left), len(right)
    left += [float("inf")]
    right += [float("inf")]
    
    marray = [0] * (len_l + len_r)
            
    l, r = 0, 0
    for i in range(len_l + len_r):
        if left[l] <= right[r]:
            marray[i] = left[l]
            l += 1
            num += r
        else:
            marray[i] = right[r]
            r += 1

    return marray

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

marge_sort(a)
print(num)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

class Inversion():
    def __init__(self):
        self.cnt = 0
    def merge(self, A, left, mid, right):
        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] = 10000000000
        R[n2] = 10000000000
        i = 0
        j = 0
        for k in range(left, right):
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                self.cnt += n1 - i
                A[k] = R[j]
                j += 1
        return self
    
    def mergesort(self, A, left, right):
        if left + 1 < right:
            mid = (left + right) // 2
            self.mergesort(A, left, mid)
            self.mergesort(A, mid, right)
            self.merge(A, left, mid, right)
        return self

a = Inversion().mergesort(A, 0, n)
print(a.cnt)

Submission status: Accepted

Solution code:
# ぶっちゃけアイデアを理解するのが難しかった。
# 詳細な解説は本を読もう
# 長さ2の配列ならば反転数をもとめるのは一瞬
# 2つの配列をソートしながらマージするときについでに反転数が求まるのが鍵で、これを実装に組み込む

INF = 10**9 + 1


def merge(A: list, left: int, mid: int, right: int) -> int:
    '''
    2つの配列をmergeする関数

    Aはこのプログラムで処理する配列。
    left, mid, rightはAのindex。
    '''
    cnt = 0  # mergeするときに何回反転するか
    n1 = mid-left  # 右の方の配列のlen (反転数を計算するときにこいつを使う)
    # n2 = right-mid  # 左の方の配列のlen ぶっちゃけいらない

    L = A[left:mid]  # python sliceはshallow copyらしい
    L.append(INF)  # 番兵
    R = A[mid:right]
    R.append(INF)  # 番兵

    i_l, i_r = 0, 0  # LとRのコントロール用idx
    for k in range(left, right):
        # L,Rの先頭を比較していって小さい方をAに打ち込む
        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: list, left: int, right: int):
    '''
    マージソートをしつつ、反転数を再帰的に計算する。

    ここではマージを再帰的に適応し反転数をどんどん上に伝播させていく仕組み
    '''
    if left + 1 >= right:  # 終了条件
        return 0

    mid = (left+right)//2
    v1 = merge_sort(A, left, mid)  # 右左にも再帰的にmerge_sortを適応
    v2 = merge_sort(A, mid, right)
    v3 = merge(A, left, mid, right)  # 右左整ったらmerge

    return v1+v2+v3


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