Spoj INVCNT Solution

Inversion Count Solution

#include<bits/stdc++.h>

#define N 10000009

#define ll long long int

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

ll tree[N], a[N];

ll query(int indx)

{

    ll sum = 0;

    while(indx > 0)

    {

        sum += tree[indx];

        indx -= (indx & (-indx));

    }

    return sum;

}

void update(int indx, int value, int n)

{

    while(indx <= n)

    {

        tree[indx] += value;

        indx += (indx & (-indx));

    }

}

ll invcnt(int n, ll mx)

{

    ll cnt = 0;

    for(int i=n-1; i>=0; i--)

    {

        cnt += query(a[i]-1);

        update(a[i], 1, mx);

    }

    return cnt;

}

void clears(int n)

{

    for(int i=0; i<=n; i++)

        tree[i] = a[i] = 0;

}

int main()

{

    fast

    int t;

    cin >> t;

    while(t--)

    {

        int n;

        cin >> n;

        ll mx = 0;

        for(int i=0; i<n; i++)

        {

            cin >> a[i];

            mx = max(a[i], mx);

        }

        cout << invcnt(n, mx) << "\n";

        clears(mx);

    }

    return 0;

}