[SPOJ] INVERSION COUNT

help
, ,
1

The Question Link is :-

My Solution Link is :-1

I don’t what is wrong with my Solution i have done what is necessary for inversion count.
Help me where i am Wrong.

2

I think on line number 32 when you are updating ans as ans += middle-i, it should be ans += n1-i.
I haven’t solve the problem using merge sort. I use Binary Indexed tree.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll getSum(ll BITree[], ll index)
{
ll sum = 0;
while (index > 0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(ll BITree[], ll n, ll index, ll val)
{
while (index <= n)
{
BITree[index] += val;
index += index & (-index);
}
}
void convert(ll arr[], ll n)
{
ll temp[n];
for (int i=0; i<n; i++)
temp[i] = arr[i];
sort(temp, temp+n);
for (int i=0; i<n; i++)
{
arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
}
}
ll getInvCount(ll arr[], ll n)
{
ll invcount = 0;
convert(arr, n);
ll BIT[n+1];
for (int i=1; i<=n; i++)
BIT[i] = 0;
for (int i=n-1; i>=0; i–)
{
invcount += getSum(BIT, arr[i]-1);
//cout << invcount << “\n”;
updateBIT(BIT, n, arr[i], 1);
}

	return invcount; 
} 
int main() 
{
	int t;
	cin >> t;
	while(t--)
	{
		ll n;
		cin >> n;
		ll arr[n];
		for(int i=0;i<n;i++)
			cin >> arr[i];
		cout << getInvCount(arr,n) << "\n";
	}
	return 0; 
}
1 Like
3

I never thought that this could be solved by BIT :wink:

1 Like
4

You are Right. First it will be n1. I solved using merge sort and now i will try using bit.

1 Like
5

I will do that also. Thanks.

6

:咯咯地笑: