gistfile1.txt

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define maxn 300001

typedef long long bigNum;
bigNum tree[maxn], data[maxn], sorted[maxn];

using namespace std;

bigNum read(int idx);

void update(int idx, bigNum value, int arraysize);

int main()
{
    int testcases, arraySize, value, invCount;
    cin >> testcases;
    for(int i = 0; i<testcases; ++i){
        invCount = 0;
        cin >> arraySize;
        for(int j = 0; j < arraySize; ++j){
            cin >> data[j];
            sorted[j] = data[j];
        }
        memset(tree, 0, sizeof tree);
        sort(sorted, sorted + arraySize);
        for(int j = 0; j < arraySize; ++j){
            value = int(lower_bound(sorted, sorted + arraySize, data[j]) - sorted);
            data[j] = value + 1;
        }
        for(int j = arraySize - 1; j >= 0; --j){
            bigNum c = read(data[j] - 1);
            invCount += c;
            update(data[j], 1, arraySize);
        }
        cout << invCount << endl;
    }
}

bigNum read(int idx)
{
    bigNum i = 0;
    while(idx > 0){
        i += tree[idx];
        idx -= (idx & -idx);
    }
    return i;
}

void update(int idx, bigNum value, int arraysize)
{
    while(idx <= arraysize){
        tree[idx] += value;
        idx += (idx & -idx);
    }
}