SPOJ Inversion Count

Problem Summary:

Let A[0…n – 1] be an array of n distinct positive integers. If i A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Full Problem Description is here.

A Very Nice Analysis is Here

Merge Sort Solution


/*
Algorithm: Solution with Merge Sort. This problem can also be solved
            with BST and BIT.
*/
 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL a[200009];
LL ans=0;
void Merge(LL left_begin,LL left_end,LL right_begin,LL right_end)
{
    LL pos=0,pp=left_begin;
    LL temp[right_end-left_begin+3];
    while(left_begin<=left_end&&right_begin<=right_end)
    {
        if(a[left_begin]<=a[right_begin])
            temp[pos++]=a[left_begin++];
        else
        {
            ans=ans+(left_end-left_begin+1);
            temp[pos++]=a[right_begin++];
        }
    }
    while(left_begin<=left_end) temp[pos++]=a[left_begin++];
    while(right_begin<=right_end) temp[pos++]=a[right_begin++];
    for(LL i=0;i<pos;i++)
        a[pp+i]=temp[i];
    return;
}
 
void MergeSort(LL left,LL right)
{
    LL mid=(left+right)>>1;
    if(left<right)
    {
        MergeSort(left,mid);
        MergeSort(mid+1,right);
        Merge(left,mid,mid+1,right);
    }
}
 
int main()
{
    LL i,j,k,n,m,d,test,t=0;
    scanf("%lld",&test);
    while(test--)
    {
        ans=0;
        scanf("%lld",&n);
        for(i=0;i<n;i++)
            scanf("%lld",&a[i]);
        MergeSort(0,n-1);
        printf("%lld\n",ans);
    }
    return 0;
}

BIT Solution

/*
Algorithm: Binary Indexed Tree
*/
 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
 
LL a[200009];
LL b[200009];
LL tree[200009];
LL n;
 
void update(LL idx,LL val)
{
    while(idx<=n)
    {
        tree[idx]+=val;
        idx+=idx&-idx;
    }
}
 
LL query(LL idx)
{
    LL ret=0;
    while(idx>0)
    {
        ret+=tree[idx];
        idx-=idx&-idx;
    }
    return ret;
}
 
int main()
{
    LL i,j,k,m,d,test,t=0;
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld",&n);
        memset(tree,0,sizeof(tree));
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            b[i]=a[i];
        }
        sort(b,b+n);
        for(i=0;i<n;i++)
        {
            d=lower_bound(b,b+n,a[i])-b;
            a[i]=d+1;
        }
        LL ans=0;
        for(i=n-1;i>=0;i--)
        {
            ans=ans+query(a[i]-1);
            update(a[i],1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
 

This Problem UVA-10810 – Ultra-QuickSort can also be solved with these above two solutions.

Advertisements
About

ACM Competitive Programmer

Posted in Binary Indexed Tree, SPOJ, UVA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog Stats
Recent Posts
Recent Comments
Larry Page on An Easy DP Problem-2 with…
Anonymous on An Easy DP Problem-2 with…
Kaiser on An Easy DP Problem-1
Categories
Archives

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 9 other followers

%d bloggers like this: