INVCNT - Inversion Count

                                                 INVCNT - Inversion Count

Topic: BIT

	#include<bits/stdc++.h>
	using namespace std;
	const int maxn = 10000007;
	typedef long long LL;
	long long getSum(LL BITree[], LL idx)
	{
	long long sum = 0;
	while(idx > 0){
	sum += BITree[idx];
	idx -= idx & (-idx);
	}
	return sum;
	}
	LL updateBIT(LL BITree[], LL n, LL idx, LL val)
	{
	while(idx <= n){
	BITree[idx] += val;
	idx += idx & (-idx);
	}
	}
	void convert(LL a[], LL n)
	{
	LL t[n];
	for(LL i = 0; i < n; i++){
	t[i] = a[i];
	}
	sort(t, t+n);
	for(LL i =0; i < n; i++){
	a[i] = lower_bound(t, t+n, a[i]) - t + 1;
	}
	}
	long long countInversions(LL a[], LL n)
	{
	long long cnt = 0;
	convert(a, n);
	long long bit[n+1];
	for(LL i = 1; i <= n; i++){
	bit[i] = 0;
	}
	for(LL i = n - 1; i >= 0; i--){
	cnt += getSum(bit, a[i] - 1);
	updateBIT(bit, n, a[i], 1);
	}
	return cnt;
	}
	int main()
	{
	// freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	LL T;
	cin >> T;
	while(T--)
	{
	LL n;
	cin >> n;
	LL a[n+5];
	for(LL i =0; i < n; i++)
	{
	cin >> a[i];
	}
	cout << countInversions(a, n)<<endl;
	}
	return 0;
	}

view raw InversionCountUsing BIT.cpp hosted with ❤ by GitHub

Share: