CODESPTB - Insertion Sort - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : CODESPTB

👉 Hint : Segment Tree with Lazy Propagation

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
 
ll arr[100001];
ll ans=0;
ll tmp[100001];
 
void Merge(ll l,ll m,ll r)
{
    ll i=l,j=m+1,k=0;
    while(i<=m && j<=r)
    {
        if(arr[i]>arr[j])
        {
            ans+=m-i+1;
            tmp[k++]=arr[j++];
        }
        else
            tmp[k++]=arr[i++];
            
    }
    while(i<=m)
        tmp[k++]=arr[i++];
    while(j<=r)
        tmp[k++]=arr[j++];
    k=0;
    for(i=l;i<=r;i++)
        arr[i]=tmp[k++];
}
 
void MergeInv(ll l,ll r)
{
    if(l<r)
    {
        ll m=(l+r)/2;
        MergeInv(l,m);
        MergeInv(m+1,r);
        Merge(l,m,r);
    }
}
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ans=0;
        for(ll i=0;i<n;i++)
            cin>>arr[i];
        MergeInv(0,n-1);
        cout<<ans<<endl;
 
    }
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.