counting inversions same as uva11495

uva10810.cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>

using namespace std;



typedef long long ll;

ll c_i;

template <class T>
void Merge(T a[],T temp[],ll low,ll high)
{
    ll mid=(high+low)/2;
    ll i=low;
    ll j=mid+1;
    ll k=low;

    while(i<=mid && j<=high)
    {
        if(a[i]<=a[j])
            temp[k++]=a[i++];
        else
        {
            temp[k++]=a[j++];
            c_i+=(mid-i+1);
        }
    }

    while(i<=mid) temp[k++]=a[i++];
    while(j<=high) temp[k++]=a[j++];

    //copy back temp in
    for(ll z=low;z<=high;z++) a[z]=temp[z];
}

template <class T>
void MergeSort(T a[],T temp[],ll low,ll high)
{
    if(low<high)
    {
        ll mid=(low+high)/2;
        MergeSort(a,temp,low,mid);
        MergeSort(a,temp,mid+1,high);
        Merge<T>(a,temp,low,high);

    }

}


int main()
{
    ll a[500001],t[500001];
    while(1)
    {
        ll n;
        cin>>n;
        if(n==0) break;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        c_i=0;
        MergeSort<ll>(a,t,1,n);

//        for(int i=1;i<=n;i++)
//            cout<<a[i]<<"   ";
        cout<<c_i<<endl;

    }

    return 0;
}