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 get_num_inversions(A, left, right):
    num_inversions = 0
    if right - left <= 1:
        return num_inversions

    mid = (left+right) // 2
    num_inversions += get_num_inversions(A, left, mid)
    num_inversions += get_num_inversions(A, mid, right)
    num_inversions = merge(A, left, mid, right, num_inversions)

    return num_inversions


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

    L.append(1e10)
    R.append(1e10)

    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
            num_inversions += len(L) - i - 1 # -1はappendした1e10の分

    return num_inversions


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
cnt = 0
n = int(input())
S = list(map(int, input().split()))

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)

def merge(S, left, mid, right):

  L = S[left:mid] + [10**10]
  R = S[mid:right] + [10**10]

  i,j = 0,0

  global cnt
  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 += len(L) -1 - i

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

Submission status: Accepted

Solution code:
MAX = 200000
INF = 10 ** 10
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]
          i +=  1
        else:
          A[k] = R[j]
          j +=  1
          cnt += mid - left - i
    return cnt

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

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

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(10 ** 9)
    R.append(10 ** 9)
    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 += (len(L) - 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)

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

print(count)

Submission status: Accepted

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

from collections import defaultdict

class BIT:
    # 1-indexedに注意！
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
# 使用例
# bit = BIT(10)     # 要素数を与えてインスタンス化
# bit.add(2, 10)    # a2に10を加える
# bit.add(5, 5)     # a5に 5を加える
# print(bit.sum(3)) # a1～a3の合計を返す => 10
# print(bit.sum(6)) # a1～a6の合計を返す => 15
# bit.add(3, -6)    # a3に-6を加える
# print(bit.sum(6)) # a1～a6の合計を返す => 9
# print(bit.sum(6) - bit.sum(3))  # a4～a6の合計 => 5
# bit.add(10,7)     # a10に7を加える
# print(bit.sum(10))# a1〜a10の合計を返す => 16

bit = BIT(n)

b = sorted(a)
# print(b)

d = defaultdict(int)
for i in range(n):
    d[b[i]] = i
# print(list(d))

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

print(ans)

Submission status: Accepted

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

  l = array[left:mid]
  r = array[mid:right]

  l.append(9999999999)
  r.append(9999999999)

  i, j = 0, 0

  for k in range(left, right):
    if l[i] <= r[j]:
      array[k] = l[i]
      i += 1
    else:
      array[k] = r[j]
      cnt += n1 - i
      j += 1
  
  return cnt

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def merge(A, left, mid, right, cnt):
    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] = math.inf
    R[n2] = math.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
            cnt += mid - left - i
            
    return A, cnt


def mergeSort(A, left, right, cnt):
    if left+1 < right:
        mid = (left + right)//2
        A, cnt = mergeSort(A, left, mid, cnt)
        A, cnt = mergeSort(A, mid, right, cnt)
        A, cnt = merge(A, left, mid, right, cnt)
    return A, cnt
        
n = int(input())
A= list(map(int,input().split()))

A_out, cnt_out = mergeSort(A,0,len(A),0)

print(str(cnt_out))

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:
INF = pow(10, 18)

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

    i = 0
    j = 0
    cnt = 0
    n1 = mid - left
    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 merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = merge_sort(A, left, mid)
        cnt2 = merge_sort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0

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

Submission status: Accepted

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

cnt = 0

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

  global cnt
  L = A[left:mid]
  L.append(math.inf)
  R = A[mid:right]
  R.append(math.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 += len(L) -1 -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(A,0,n)

print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
A=tuple(map(int,input().split()))
cnt=0
def merge_sort(A,n):
    if n == 1:
        return A
    else:
        global cnt
        mid=(n+1)//2
        nl=len(A[:mid])
        nr=len(A[mid:])
        L=merge_sort(A[:mid],nl)
        R=merge_sort(A[mid:],nr)
        nli=0
        nri=0
        ans=[0]*(nl+nr)
        i=0
        while i < n:
            if nli == nl:
                ans[i]=R[nri]
                nri += 1
            elif nri == nr:
                ans[i]=L[nli]
                nli += 1
            elif L[nli] <= R[nri]:
                ans[i]=L[nli]
                nli += 1
            else:
                ans[i]=R[nri]
                nri += 1
                cnt += nl-nli
            i += 1
        return tuple(ans)
                



merge_sort(A,n)
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

snt = 10 ** 9 + 1

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

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

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

Submission status: Accepted

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


# MAX = 200000
SENTINEL = 10 ** 9 + 1
# L = [0] * (MAX // 2 + 2)
# R = [0] * (MAX // 2 + 2)

L = [0] * (n // 2 + 2)
R = [0] * (n // 2 + 2)

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

def merge_sort(A, left, right):
	# n = len(A)
	if left + 1 < right:
		mid = (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
	return 

cnt = 0
# print(A)
merge_sort(A, 0, n)
# print(A)
print(cnt)

Submission status: Accepted

Solution code:
def merge(arr, l, mid, r):
    L = [arr[i] for i in range(l, mid)]
    R = [arr[i] for i in range(mid, r)]
    L.append(int(1e9 + 10))
    R.append(int(1e9 + 10))
    i, j = 0, 0
    cnt = 0
    for k in range(l, r):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
            cnt += len(L) - i -1
    return cnt

def mergeSort(arr, l, r):
    cnt = 0
    if l + 1 < r:
        mid = (l + r) >> 1
        cnt += mergeSort(arr, l, mid)
        cnt += mergeSort(arr, mid, r)
        cnt += merge(arr, l, mid, r)
    return cnt

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

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
c = 0


def merge(left, mid, right):
    global c
    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
            c += mid - left - i


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


merge_sort(0, n)

print(c)

Submission status: Accepted

Solution code:
c = 0

def merge(a,l,m,r):
    global c
    n1 = m-l
    n2 = r-m
    L = a[l:m]
    R = a[m:r]
    L.append(1000000009)
    R.append(1000000009)
    i,j = 0,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 += n1-i

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  # 1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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


if __name__ == "__main__":
    N = int(input())
    bit = BinaryIndexTree(N+10)

    A = list(map(int, input().split()))
    d = {a: i+1 for i, a in enumerate(sorted(A))}

    ans = 0
    for a in A:
        i = d[a]
        ans += (i - bit.sum(i) - 1)
        bit.add(i, 1)
    print(ans)

Submission status: Accepted

Solution code:
INF = 10**9 + 1
def merge(A: list, left: int, mid: int, right: int) -> int:
  cnt = 0
  n1 = mid - left

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

  i_l, i_r = 0, 0
  for k in range(left, right):
    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)
  v2 = merge_sort(A, mid, right)
  v3 = merge(A, left, mid, right)

  return v1 + v2 + v3

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

Submission status: Accepted

Solution code:
inv_count = 0

def Merge(A, left, mid, right):
    global inv_count

    sentinel = 2000000000
    n1 = mid - left
    n2 = right - mid
    L = A[left : left + (mid - left)] + [sentinel] 
    R = A[mid : mid + (right - mid)] + [sentinel]
    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
            inv_count += (n1 - 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)

def Main():
    N = input()
    A = [int(a) for a in input().split()]
    MergeSort(A, 0, len(A))
    global inv_count
    print(inv_count)

Main()

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.bit = [0] * (n + 1) # don't use bit[0]
        else:
            self.bit = [0] + init
            for i in range(1, n):
                self.bit[i + (i & -i)] += self.bit[i]

    def sum(self, i):
        '''
        Calculate bit[1] + ... + bit[i]
        '''
        S = 0
        while i > 0:
            S += self.bit[i]
            i -= i & -i
        return S

    def add(self, i, x):
        '''
        set bit[i] to be bit[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
def inversion_number(A):
    inv = 0
    bit = BIT(len(A))
    for i, x in enumerate(coord_compress(A)):
        inv += i - bit.sum(x+1)
        bit.add(x+1, 1)
    return inv

N = int(input())
*A, = map(int, input().split())
print(inversion_number(A))

Submission status: Accepted

Solution code:
# The Number of Inversions
N = int(input())
A = list(map(int, input().split()))
INF = float('inf')
cnt = 0


def merge(left, mid, right):
    global cnt
    L = A[left:mid]+[INF]
    R = A[mid:right]+[INF]
    l = 0
    r = 0
    nl = mid - left

    for i in range(right-left):
        if L[l] < R[r]:
            A[left+i] = L[l]
            l += 1
        else:
            A[left+i] = R[r]
            r += 1
            cnt += nl - l


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


merge_sort(0, N)
print(cnt)

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 partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            i = i + 1
            (A[i], A[j]) = (A[j], A[i])

    (A[i+1], A[r]) = (A[r], A[i+1])

    return i+1
    
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def stable(A, B):
    for i in range(len(A)):
        if A[i] != B[i]:
            return "Not stable"
    return "Stable"

def merge(A, left, mid, right):
    count = 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(10**9)
    R.append(10**9)

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

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

n = int(input())
X = list(map(int, input().split()))
x = mergeSort(X, 0, n)

print(x)

Submission status: Accepted

Solution code:


def merge(num_list,left,right,cnt):
    mid = (left+right)//2
    L = num_list[left:mid][:]
    R = num_list[mid:right][:]
    L.append(float("inf"))
    R.append(float("inf"))
    i = 0
    j = 0

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

def merge_sort(num_list,left,right,cnt):
    mid = (left+right)//2
    if left+1 < right:
        cnt_l = merge_sort(num_list,left,mid,cnt)
        cnt_r = merge_sort(num_list,mid,right,cnt)
        cnt_all = cnt_l+cnt_r
        cnt = merge(num_list,left,right,cnt_all)

    return cnt

if __name__ == "__main__":
    n = int(input())
    cnt = 0
    num_list = list(map(int,input().split()))
    cnt = merge_sort(num_list,0,len(num_list),cnt)
    print(cnt)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def 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()
x_to_i = {x: i for i, x in enumerate(sorted(set(a)))}
a = [x_to_i[x]+1 for x in a]
ans = 0
bit = Bit(N)

for j in range(N):
    ans += j-bit.sum(a[j])
    bit.add(a[j], 1)
print(ans)

Submission status: Accepted

Solution code:
inf = 10**9 + 7


def merge(L, R):
    cnt = 0
    l, r = len(L), len(R)
    L.append(inf)
    R.append(inf)
    lst = []
    i, j = 0, 0
    for k in range(l + r):
        if L[i] < R[j]:
            lst.append(L[i])
            i += 1
        else:
            lst.append(R[j])
            j += 1
            # まだ追加されていないLの要素数
            cnt += l - i
    return lst, cnt


def merge_sort(A):
    l = len(A)
    if l == 1:
        return A, 0
    L, cntL = merge_sort(A[:l // 2])
    R, cntR = merge_sort(A[l // 2:])
    A, cnt = merge(L, R)
    return A, cntL + cntR + cnt


n = int(input())
*A, = map(int, input().split())
A, cnt = merge_sort(A)
print(cnt)

Submission status: Accepted

Solution code:
INFTY=1000000000

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

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

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

cnt=mergeSort(A,0,n)
print(cnt)

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:
INF = int(1e9)
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    n = len(A)
    L = A[left:mid] + [INF] 
    R = A[mid:right] + [INF]
    i = 0
    j = 0
    cnt = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            cnt = 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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N = int(input())
S = [int(i) for i in input().split()]
INF = 10**10

def merge(s, l, m, r):
    cnt = 0
    s1 = list(s[l:m])
    s2 = list(s[m:r])

    s1.append(INF)
    s2.append(INF)
    
    i = 0
    j = 0
    for k in range(l, r):
        #print(s1, s2)
        if s1[i] <= s2[j]:
            s[k] = s1[i]
            i += 1
        else:
            s[k] = s2[j]
            j += 1
            cnt += (m - l - i)
    return cnt

def merge_sort(s, l, r, cnt):
    if l + 1 < r:
        m =  (l + r) // 2
    
        cnt = merge_sort(s, l, m, cnt)
        cnt = merge_sort(s, m, r, cnt)
    
        cnt += merge(s, l, m, r)
    return cnt
    
cc = merge_sort(S, 0, len(S), 0)
print(cc)

Submission status: Accepted

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

SWAP = 0

def conquer(A, left, mid, right):
  L, R = A[left:mid], A[mid:right]
  # L, Rの末尾にINFTYを入れないと、L[-1] or R[-1]が評価されない
  INFTY = 2 ** 30
  L.append(INFTY)
  R.append(INFTY)
  # i : position in L, j : position in R
  i, j = 0, 0

  swap_times =  0

  # 元のArrayを変えたいため、kを生成
  for k in range(left, right):
    # print(i, j, L, R, A)
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1
      swap_times += (mid-left) - i

  return swap_times

def divide(A, left, right):
  # print(left, right)

  # A[right-left]が2つ以上の場合に
  if left+1 < right:
    mid = (left+right)//2

    countL = divide(A, left, mid)
    countR = divide(A, mid, right)

    return conquer(A, left, mid, right) + countL + countR

  return 0

def mergeSort(A):
  return divide(A, 0, len(A))

swap = mergeSort(A)
print(swap)

Submission status: Accepted

Solution code:
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9


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

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

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


# def bubble_sort(a):
#     count = 0
#     for i in range(len(a)):
#         for j in range(len(a) - 1, i, -1):
#             if a[j] < a[j - 1]:
#                 a[j - 1], a[j] = a[j], a[j - 1]
#                 count = count + 1
#     return count


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

    sorted_a = sorted(a)
    map_a = {}
    for i in range(n):
        map_a[sorted_a[i]] = i
    flat_a = list(map(lambda x: map_a[x], a))
    # print(map_a)
    # print(flat_a)

    bit = BIT(n)
    count = 0
    for i in range(n):
        bit.add(flat_a[i] + 1, 1)
        count = count + i + 1 - bit.sum(flat_a[i] + 1)
    print(count)


if __name__ == '__main__':
    main()

# 3 5 2 1 4
# 2 4 1 0 3
#     1|
#     1   1|
#   1|1   1
# 1|1 1   1
# 1 1 1 1|1

Submission status: Accepted

Solution code:
global input_n
global input_data
global result

#インプットdata
input_n = int(input())
input_data = list(map(int, input().split()))
result = 0

#バブルソートプログラム
def bubbleSort():
    global result
    for i in range(input_n):
        jude = result
        for j in range(input_n-1, i, -1):
            if input_data[j] < input_data[j-1]:
                input_data[j], input_data[j-1] = input_data[j-1], input_data[j]
                result += 1
        if jude == result: break

#アルゴリズム：ソート
def merge(left, mid, right):
    global result
    
    n1 = mid - left
    n2 = right - mid
    inf = 10**9
    L_list = input_data[left: mid] + [inf]
    R_list = input_data[mid: right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        if L_list[i] <= R_list[j]:
            input_data[k] = L_list[i]
            i += 1
        else:
            input_data[k] = R_list[j]
            j += 1
            result += n1 - i

#アルゴリズム：マージソート
def mergeSort(left, right):
    if (left + 1) < right:
        mid = (left + right) // 2
        mergeSort(left, mid)
        mergeSort(mid, right)
        merge(left, mid, right)

#処理の実行
#bubbleSort()
mergeSort(0, input_n)
print(result)

Submission status: Accepted

Solution code:
# 長さ1の配列ならば反転数は0
# 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))