invcnt.c

#include <stdio.h>


long long int temp_array[200005];

long long int split_inversions(long long int a[], long long int lo, long long int hi)
{
    if(hi - lo <= 1)
        return 0;
    long long int mid = lo + (hi - lo) / 2;
    long long int i = lo;
    long long int j = mid;
    long long int inv = 0;
    long long int k = lo;
    while(i < mid && j < hi)
    {
        if (a[i] > a[j])
        {
            inv += mid - i;
            temp_array[k++] = a[j++];
        }
        else
        {
            temp_array[k++] = a[i++];
        }
    }
    while(i < mid)
    {
        temp_array[k++] = a[i++];
    }
    while(j < hi)
    {
        temp_array[k++] = a[j++];
    }
    for(i = lo; i < hi; i++)
        a[i] = temp_array[i];
    return inv;
}
long long int inversions(long long int a[], long long int lo, long long int hi)
{
    if (hi - lo <= 1)
        return 0;
    long long int inv;
    inv = inversions(a, lo, lo + (hi - lo) / 2);
    inv += inversions(a, lo + (hi - lo) / 2, hi);
    inv += split_inversions(a, lo, hi);
    return inv;
}

long long int get_int(long long int n)
{   
    int sign=1;
    char c=0;
    while(c<33)
        c=getchar_unlocked();
    if (c=='-')
    {
        sign=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        n=(n<<3)+(n<<1)+(c-'0');
        c=getchar_unlocked();
    }
return n*sign;
}

int main(int argc, const char *argv[])
{
    long long int tests, n, i;
    tests = get_int(0);
    while (tests--)
    {
        n = get_int(0);
        long long int a[n];
        for (i = 0; i < n; i++)
            a[i] = get_int(0);
        printf("%lld\n", inversions(a, 0, n));
    }
    return 0;
}

invcnt.py

from bisect import bisect


def inversions(a):
    t = []
    count = 0
    for x in xrange(len(a)):
        i = bisect(t, a[x])
        t.insert(i, a[x])
        count += x - i
    return count

temp_array = [0]*200000


def split_inversions(a, lo, hi):
    if hi - lo <= 1:
        return 0
    mid = lo + (hi - lo) // 2
    i = lo
    j = mid
    inv = 0
    k = lo
    while i < mid and j < hi:
        if a[i] > a[j]:
            inv += mid - i
            temp_array[k] = a[j]
            j += 1
            k += 1
        else:
            temp_array[k] = a[i]
            i += 1
            k += 1
    while i < mid:
        temp_array[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        temp_array[k] = a[j]
        j += 1
        k += 1
    for x in xrange(lo, hi):
        a[x] = temp_array[x]
    return inv


def count_inversions(a, l, h):
    if h - l <= 1:
        return 0
    inv = count_inversions(a, l, l + (h - l) // 2)
    inv += count_inversions(a, l + (h - l) // 2, h)
    inv += split_inversions(a, l, h)
    return inv


class Bit:
    def __init__(self, n):
        sz = 1
        while n > sz:
            sz *= 2
        self.size = sz
        self.data = [0]*sz

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

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


def count_inversion_using_BIT(a):
    res = 0
    bit = Bit(max(a)+1)
    for i, v in enumerate(a):
        res += i - bit.sum(v)
        bit.add(v, 1)

    return res

for tests in xrange(int(raw_input())):
    raw_input()
    n = int(raw_input())
    a = []
    append = a.append
    for x in xrange(n):
        append(int(raw_input()))
    print count_inversion_using_BIT(a)