UVA 10810 / Merge Sort Technique

/***
 created: 2022-04-13-13.07.36
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'
ll a[500005],ans;

void mergearray(ll l,ll mid,ll r)
{
    ll n1=mid-l+1;
    ll n2=r-mid;

    ll x[n1+2],y[n2+2],i,j,k;

    for(i=0; i<n1; i++)
    {
        x[i]=a[l+i];
    }

    for(i=0; i<n2; i++)
    {
        y[i]=a[mid+i+1];
    }

    i=j=0;
    k=l;

    while(i<n1 && j<n2)
    {
        if(x[i]<y[j])
        {
            a[k]=x[i];
            i++,k++;
        }
        else
        {
            ans+=(n1-i);
            a[k]=y[j];
            j++,k++;
        }
    }

    while(i<n1)
    {
        a[k]=x[i];
        i++,k++;
    }

    while(j<n2)
    {
        a[k]=y[j];
        j++,k++;
    }
}

void mergesort(ll l,ll r)
{
    if(l<r)
    {
        ll mid=(l+r)/2;

        mergesort(l,mid);
        mergesort(mid+1,r);

        mergearray(l,mid,r);
    }
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n,m,i,j,k,l;

    while(cin>>n && n)
    {
        for(i=0; i<n; i++) cin>>a[i];

        mergesort(0,n-1);

        //for(i=0; i<n; i++) cout<<a[i]<<" ";

        cout<<ans<<nl;

        ans=0;
    }



    // 3 2 1 5 6 7
    // 3 2 1 --- 5 6 7
    //    |
    // 3 2 --- 1
    // 2 3 --- 1  ans=1;
    // 2 3 --- 1
    // 1 2 3   ans=2;

    get_lost_idiot;
}