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:
infty = 1000000000
count = 0

def merge(A, left, mid, right):
	global count
	L = A[left:mid]
	R = A[mid:right]
	L.append(infty)
	R.append(infty)
	i = 0
	j = 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
			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)


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

Submission status: Accepted

Solution code:
# AOJ ALDS1_5_D "The Number of Inversions"
# 転倒数をO(NlogN)で求める

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

# binary indexed tree
bit = [0 for _ in range(N+1)]

# 0からiまでの区間和
# 立っているビットを下から処理
def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

# i番目の要素にxを足す
# 覆ってる区間すべてに足す
def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i

# 座標圧縮
ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i+1

# それまでに「i<=jかつai<=aj」となっているものをBITに加えていく
ans = 0
for j, a in enumerate(A):
    ind_a = co_to_ind[a]
    ans += j - query_sum(ind_a)
    add(ind_a, 1)

print(ans)

Submission status: Accepted

Solution code:
# ALDS1_5_D The Number of Inversions
import sys
count = 0


def mearge(A, left, p, right):
    global count
    l = A[left: p]
    r = A[p: right]

    l.append(float('inf'))
    r.append(float('inf'))

    i = 0
    j = 0

    for k in range(left, right, 1):
        if l[i] <= r[j]:
            A[k] = l[i]
            i += 1
            count += j
        else:
            A[k] = r[j]
            j += 1


def mearge_sort(A, left, right):
    if left + 1 < right:
        p = (left + right) // 2
        mearge_sort(A, left, p)
        mearge_sort(A, p, right)
        mearge(A, left, p, right)


n = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
mearge_sort(A, 0, n)
print(count)

Submission status: Accepted

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

def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0
    else:
        a = arr[:len(arr)//2]
        b = arr[len(arr)//2:]
        a, ai = mergeSortInversions(a)
        b, bi = mergeSortInversions(b)
        c = []
        i = 0
        j = 0
        inversions = 0 + ai + bi
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
            inversions += (len(a)-i)
    c += a[i:]
    c += b[j:]
    return c, inversions

c, inversions = mergeSortInversions(A)
print(inversions)

Submission status: Accepted

Solution code:
def merge(A, c, left, mid, right):
    count = 0
    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] = 2000000000
    R[n2] = 2000000000
    i = 0
    j = 0
    for k in range(left,right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else : 
            A[k] = R[j]
            j += 1
            count += n1 - i
    return count

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

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

Submission status: Accepted

Solution code:
#反転数
import math
n = int(input())
A = list(map(int, input().split()))
C = 0
INFTY = 1e9 + 1

def merge(S, left, mid, right):
    global C
    n1 = mid - left
    n2 = right - mid
    l = S[left:left + n1]
    r = S[mid:mid + n2]
    l.append(INFTY)
    r.append(INFTY)
    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]
            C += n1 - i
            j += 1
        

def merge_inverse(S, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right) / 2)
        merge_inverse(S, left, mid)
        merge_inverse(S, mid, right)
        merge(S, left, mid, right)
merge_inverse(A, 0, n)
print(C)

Submission status: Accepted

Solution code:
SENTINEL = float('inf')


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

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


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


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


def merge(A, n, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i = j = 0
    count = 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 + j - k - 1
    return count


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

infty = 10**10

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

	n1 = mid -left
	n2 = right - mid

	L = [0] * n1
	R = [0] * n2

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

	L.append(infty)
	R.append(infty)

	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:
			cnt += len(L) - 1 - i
			A[k] = R[j]
			j = j + 1
		

	return cnt

def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

		mid = (left + right) // 2
		cnt += mergeSort(A,left,mid)
		cnt += mergeSort(A,mid,right)
		cnt += merge(A,left,mid,right)

	return cnt

def test():

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

	result = mergeSort(S,0,n)
	
	print(result)


if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
class MergeSort:
    def __init__(self, array):
        self._arr = array
        self._cnt = 0

    def _merge(self, left, mid, right):
        arr1 = self._arr[left:mid] + [float('inf')]
        arr2 = self._arr[mid:right] + [float('inf')]

        i, j = 0, 0
        for k in range(left, right):
            if arr1[i] <= arr2[j]:
                self._arr[k] = arr1[i]
                i += 1
            else:
                self._arr[k] = arr2[j]
                j += 1
                self._cnt += len(arr1) - i - 1


    def _merge_sort(self, left, right):
        if right <= left + 1:
            return

        mid = (left + right) // 2
        self._merge_sort(left, mid)
        self._merge_sort(mid, right)
        self._merge(left, mid, right)

    def sort(self):
        self._merge_sort(0, len(self._arr))

    def print(self):
        # print(*self._arr)
        print(self._cnt)

n = int(input())
arr = [int(s) for s in input().split()]

alg = MergeSort(arr)
alg.sort()
alg.print()

Submission status: Accepted

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


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    INF = 10**9
    global cnt
    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 += 1
        else:
            A[k] = R[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)
        
n = int(input())
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
 
def marge(A, left, mid, right):
    global 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] = pow(10,10)
    R[n2] = pow(10,10)
     
    l = 0
    r = 0
    for k in range(left, right):
        if L[l] <= R[r]:
            A[k] = L[l]
            l += 1
        else:
            A[k] = R[r]
            r += 1
            cnt += n1 - l
            
def margeSort(A, left, right):
    if 2 <= right - left:
        mid = (left + right)//2
        margeSort(A, left, mid)
        margeSort(A, mid, right)
        marge(A, left, mid, right)
     
         
margeSort(a, 0, len(a))
print(cnt)

Submission status: Accepted

Solution code:

SENTINEL = 2000000000

def merge(arr, length, left, mid, right):

    cnt = 0

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

    L.append(SENTINEL)
    R.append(SENTINEL)

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

def merge_sort(arr, length, left, right):
    if (left + 1 < right):
        mid = (left + right)//2
        v1 = merge_sort(arr, length, left, mid)
        v2 = merge_sort(arr, length, mid, right)
        v3 = merge(arr, n, left, mid, right)
        return v3 + v2 + v1
    else:
        return 0    

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

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

Submission status: Accepted

Solution code:
from typing import List


def g(elements: List[int], l: int, m: int, r: int) -> None:
    global inversion_num
    sentinel = 1000000000
    L, R = elements[l:m] + [sentinel], elements[m:r] + [sentinel]
    i = j = 0
    for k in range(l, r):
        if L[i] < R[j]:
            elements[k] = L[i]
            i += 1
            inversion_num += j
        else:
            elements[k] = R[j]
            j += 1


def s(elements: List[int], l: int, r: int) -> None:
    if l + 1 < r:
        m = (l + r) // 2
        s(elements, l, m)
        s(elements, m, r)
        g(elements, l, m, r)
    else:
        return


if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    inversion_num = 0

    s(elements, 0, n)

    print(f"{inversion_num}")

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=[[A[i],i+1] for i in range(n)]
B.sort()
A=[j for i,j in B]

bit=[0]*(n+1)
def add(a,w):
    x=a
    while(x<=n):
        bit[x]+=w
        x+= x&(-x)
def sum(a):
    ret=0
    x=a
    while(x>0):
        ret+=bit[x]
        x-=x&(-x)
    return ret
ans=0
for i in range(n):
    ans+=i-sum(A[i])
    add(A[i],1)
print(ans)

Submission status: Accepted

Solution code:

INF = 10**9 + 1


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

    i = 0
    j = 0
    k = left
    cnt = 0  # inversions between left half and right half
    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 right - left == 1:
        # only one element, already sorted, and inversion is zero
        return 0
    mid = (left + right) / 2
    cnt1 = merge_sort(A, left, mid)  # inversions within left half
    cnt2 = merge_sort(A, mid, right)  # inversions within right half
    # inversions between left half and right half
    cnt3 = merge(A, left, mid, right)
    return cnt1 + cnt2 + cnt3


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

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

def merge(A, left, mid, right):
    count = 0

    L = A[left:mid] + [BIG_NUM]
    R = A[mid:right] + [BIG_NUM]
    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 += len(L)-1-i
    return count

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())
A = list(map(int,input().split()))
cnt=0
cnt = mergeSort(A,0,n)
#print(*A)
print(cnt)

Submission status: Accepted

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

def g(A,l,m,r):
  global c
  L,R = A[l:m]+[1e11],A[m:r]+[1e11]
  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

s(A,0,n)
print(c)

Submission status: Accepted

Solution code:
INFTY = 1000000001

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

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

    L.append(INFTY)
    R.append(INFTY)

    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 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 = int(input())
S = list(map(int, input().split()))

cnt = 0

merge_sort(S, 0, n)


print(cnt)

Submission status: Accepted

Solution code:
def inversion(l,r):
    if l == r:
        return [lis[l]],0
    if l+1 == r:
        L=lis[l]
        R=lis[r]
        if L < R:
            return [L,R],0
        else:
            return [R,L],1
    else:
        m = (l+r)//2
        lis1,c1 = inversion(l,m)
        lis2,c2 = inversion(m+1,r)
        reslis,cres = merge(lis1,lis2)
        return reslis,c1+c2+cres

def merge(lis1,lis2):
    len1=len(lis1)
    len2=len(lis2)
    i = 0
    j = 0
    reslis = []
    count = 0
    for _ in range(len1+len2+1):
        if i==len1 or j==len2:
            if i==len1:
                reslis = reslis + lis2[j:]
            elif j==len2:
                reslis = reslis + lis1[i:]
            break
        else:
            if lis1[i] < lis2[j]:
                reslis.append(lis1[i])
                i += 1
            elif lis1[i] > lis2[j]:
                reslis.append(lis2[j])
                j += 1
                count += len1-i
    return reslis,count

n = int(input())
lis = list(map(int,input().split()))
reslis,count = inversion(0,len(lis)-1)
print(count)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
c=0
import sys
def merge(x, y):
  i=j=0
  res = []
  while j<len(y) or i<len(x):    
    while i<len(x) and (j>=len(y) or x[i]<=y[j]):

      res.append(x[i])
      i+=1
    if j<len(y):
      global c
      res.append(y[j])
      c+=len(x)-i
    j+=1
  return res
  
def sort(x):
  if len(x)>1:
    l = sort(x[:len(x)//2])
    r = sort(x[len(x)//2:])
    merged=merge(l, r)
    return merged
  else:
    return x
input()
a=list(map(int, input().split()))
sort(a)

print(c)

Submission status: Accepted

Solution code:
def merge(a):
    if len(a) == 1:
        return a, 0
    mid = len(a) // 2
    al, cnt_l, ar, cnt_r = *merge(a[:mid]), *merge(a[mid:])
    res_cnt, res_arr = 0, []
    while 0 < len(al) and 0 < len(ar):
        if al[-1] <= ar[-1]:
            res_arr.append(al.pop())
        else:
            res_arr.append(ar.pop())
            res_cnt += len(al)
    res_arr.reverse()
    return ar + al + res_arr, res_cnt + cnt_l + cnt_r


def inversion_count(a):
    return merge(a)[1]


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree(object):
    __slots__ = ["tree", "size"]

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

    def add(self, index: int, value: int):
        tree = self.tree

        while index < len(tree):
            tree[index] += value
            index += index & -index

    def sum(self, index: int):
        tree, result = self.tree, 0

        while index:
            result += tree[index]
            index -= index & -index

        return result


def solve(A):
    bit = BinaryIndexedTree(len(A)+1)
    ans = 0
    for i, n in enumerate(A):
        ans += i - bit.sum(n-1)
        bit.add(n, 1)

    return ans


if __name__ == "__main__":
    input()
    a = list(map(int, input().split()))
    d = {n: i for i, n in enumerate(sorted(a), start=1)}
    a = [d[n] for n in a]
    print(solve(a))

Submission status: Accepted

Solution code:
import math
c = 0
l = [0] * 500000
r = [0] * 500000


def merge(a, left, mid, right):
    global c
    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] = math.inf
    r[n2] = math.inf
    i, j = 0, 0
    cnt = 0
    for k in range(left, right):
        c += 1
        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):
    cnt = 0
    if (left + 1) < right:
        mid = (left + right) // 2
        cnt += mergeSort(a, left, mid)
        cnt += mergeSort(a, mid, right)
        cnt += merge(a, left, mid, right)
    return cnt


n = int(input())
*s, = map(int, input().split())

print(mergeSort(s, 0, n))

Submission status: Accepted

Solution code:
# coding: utf-8

#BIT(Binary Indexed Tree)という高速処理があるらしい
#関連してSegment Treeなんかも重要みたい
#BITの処理は数列を大きさの順位に置き換える必要がある
class Bit:
    def __init__(self, num):
        self.size = num
        self.tree = [0] * (num + 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

n = int(input().rstrip())
A = list(map(int,input().rstrip().split()))
#Aを大きさの順のインデックスにして０をなくすために１足す
A = [i+1 for i in sorted(range(len(A)), key=A.__getitem__)]
bit = Bit(n)

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

Submission status: Accepted

Solution code:
import bisect
#int bit[n+1],n

def sum(i):#[1,i]のsumを求める
    s = 0
    while(i > 0):
        s += bit[i]
        i = i&(i-1)
    return s

def add(i,x):#i番目にxを加算 i & (-i):iの最後の1のbit
    while(i <= n):
        bit[i] += x
        i += i & (-i)

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

bit = [0]

for i in range(n):
    a[i] = bisect.bisect_left(aa,a[i])+1
    bit.append(0)

ans = 0

for i in range(n):
    ans += (i - sum(a[i]))
    add(a[i],1)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

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

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

        return res

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

# Inversion Number
def inversion_num(A):
    count = 0
    bit = BIT(max(A))
    for j in range(len(A)):
        count += j-bit.sum(A[j])
        bit.add(A[j], 1)

    return count

n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
dic = {}
for i, a_i in enumerate(sorted(a), 1):
    dic[a_i] = i

# 数の大小関係を保つように、a_iが何番目に小さいかを表すリストに変形
a = [dic[a_i] for a_i in a]
print(inversion_num(a))

Submission status: Accepted

Solution code:
INF = float('inf')

def merge(lst,left,middle,right):
    cnt = 0 

    left_lst  = lst[left:middle]+[INF]
    right_lst = lst[middle:right]+[INF]

    i,j = 0,0
    for k in range(left,right):
        if left_lst[i] <= right_lst[j]:
            lst[k] = left_lst[i]
            i += 1
        else:
            lst[k] = right_lst[j]
            j += 1
            cnt += (len(left_lst)-1)-i
    return cnt

def merge_sort(lst,left,right):
    while left+1 < right:
        middle = (left+right)//2
        left_cnt  = merge_sort(lst,left,middle)
        right_cnt = merge_sort(lst,middle,right)
        return merge(lst,left,middle,right)+left_cnt+right_cnt
    return 0

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

Submission status: Accepted

Solution code:
import sys
from typing import List
import math

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


def merge(A: List[int], left: int, mid: int, right: int) -> None:
    global cnt

    left_list = A[left:mid]
    right_list = A[mid:right]
    n_left = len(left_list)
    left_list.append(sys.maxsize)
    right_list.append(sys.maxsize)

    i = 0  # left_listのインデックス
    j = 0  # right_listのインデックス
    for k in range(left, right):
        if left_list[i] <= right_list[j]:
            A[k] = left_list[i]
            i += 1
        else:
            A[k] = right_list[j]
            j += 1
            cnt += n_left - i  # 反転数を求める。左側のリストの要素数 - i が反転してる数


def merge_sort(A: List[int], left: int, right: int) -> int:
    if left + 1 < right:
        mid = math.floor((left + right) / 2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


hikaku = 0
cnt = 0
merge_sort(S, 0, len(S))
print(cnt)

Submission status: Accepted

Solution code:
def swap(list,i,j,count):
    if(list[j]<list[i]):
        list[i],list[j]=list[j],list[i]
        count[0]+=1
        return 1
    return 0

def merge(list,left1,left2,right2,count):#ソート済みの２つの区間(list[left1]〜list[left2-1]と、list[left2]〜list[right2-1]）を結合する
    i=left1
    j=left2
    tmp_list=[]
    while(1):
        if(list[i] <=list[j]):
            tmp_list.append(list[i])
            i+=1
        else:
            tmp_list.append(list[j])
            j+=1
            count[0]+=left2-i
        if(i==left2):
            for k in range(j,right2):
                tmp_list.append(list[k])
            break
        if(j==right2):
            for k in range(i,left2):
                tmp_list.append(list[k])
            break
    for k in range(left1,right2):
        list[k]=tmp_list[k-left1]
    

                
                
    
        



def merge_sort(list,left,right,count):#list[left]からlist[right]までの要素でマージソート
    if(right  == left ):
        return None
    if(left+1 == right):
        swap(list,left,right,count)
    else:
        mid=(left + right)//2
        merge_sort(list,left,mid,count)
        merge_sort(list,mid+1,right,count)
        merge(list,left,mid+1,right+1,count)
        

n=int(input())
data=list(map(int,input().split()))
count=[0]
merge_sort(data,0,n-1,count)
print(count[0])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N = int(readline())
*A, = map(int, readline().split())

data = [0]*(N+1)
def add(k, v):
    while k <= N:
        data[k] += v
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s


ans = N*(N-1)//2
for a in map({a: i+1 for i, a in enumerate(sorted(A))}.__getitem__, A):
    ans -= get(a)
    add(a, 1)
write("%d\n" % ans)

Submission status: Accepted

Solution code:
import sys

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

nchg=0
def merge(left, mid, right):
    global a, nchg
    i=0
    j=0
    ll = a[left:mid+1]
    rr = a[mid+1:right+1]
    n1 = mid-left+1
    n2 = right-mid
    while i<n1 or j<n2:
        if i==n1:
            a[left+i+j] = rr[j]
            j += 1
            nchg += n1-i
            continue
        if j==n2:
            a[left+i+j] = ll[i]
            i += 1
            continue
        if ll[i] <= rr[j]:
            a[left+i+j] = ll[i]
            i += 1
        else:
            a[left+i+j] = rr[j]
            nchg += n1-i
            j += 1


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


mergesort(0, n-1)
print(nchg)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 30 17:27:26 2018
KyotoE
@author: maezawa
"""

n = int(input())
parray = list(map(int, input().split()))
larray = [0]*n
rarray = [0]*n


def merge(a, n, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right -mid
    for i in range(n1):
        larray[i] = a[left+i]
    for i in range(n2):
        rarray[i] = a[mid+i]
    larray[n1] = 10**10
    rarray[n2] = 10**10
    i = 0
    j = 0
    for k in range(left,right):
        if larray[i] <= rarray[j]:
            a[k] = larray[i]
            i += 1
        else:
            a[k] =rarray[j]
            j += 1
            cnt += n1 - i
    return cnt

def mergesort(a, n, left, right):
    if left+1 < right:
        mid = (left+right)//2
        v1 = mergesort(a, n, left, mid)
        v2 = mergesort(a, n, mid, right)
        v3 = merge(a, n, left, mid, right)
        return v1+v2+v3
    else:
        return 0
    
ans = mergesort(parray, n, 0, n)
print(ans)

Submission status: Accepted

Solution code:
from array import array
import bisect
import collections
import heapq
import itertools
import operator
import sys


class BIT:
    def __init__(self, n):
        self.n = n
        self.arr = array("l", [0] * (n + 1))

    def __str__(self):
        return str(self.arr.tolist())

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

    def sum(self, i, j=None):
        if j is None:
            s = 0
            while i > 0:
                s += self.arr[i]
                i -= i & -i
            return s

        if i > j:
            raise ValueError

        return self.sum(j) - self.sum(i - 1)


def main():
    n = int(sys.stdin.readline())
    nums = list(map(int, sys.stdin.readline().split()))
    d = dict((num, i) for i, num in enumerate(sorted(set(nums)), 1))
    # print(d)
    bit = BIT(n + 1)

    ans = 0
    for num in nums:
        bit.add(d[num], 1)
        # print(bit)
        ans += bit.sum(d[num] + 1, n + 1)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
c = 0

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

def marge(A, right, mid, left):
    global c
    L, R = A[right:mid], A[mid:left]
    R.append(int(10E10))
    L.append(int(10E10))
    i, j = 0, 0
    smin = int(10E10)
    nums = 0
    for k in range(right, left):
        if L[i] <= R[j]:
            if smin < L[i]:
                c = c + (len(L) - i - 1) * nums
                # for cnt in range(i, len(L) - 1):
                #     print(L[cnt], smin)
                smin,nums = int(10E10), 0
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            smin, nums = R[j], nums + 1
            j = j + 1

def marge_sort(A, right, left):
    if right + 1 < left:
        mid = math.ceil((left + right) / 2)
        marge_sort(A, right, mid)
        marge_sort(A, mid, left)
        marge(A, right, mid, left)

marge_sort(A, 0, n)
print(c)