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.

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.

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

I never thought that this could be solved by BIT

1 Like

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

1 Like

I will do that also. Thanks.

:咯咯地笑: