Inversion Count

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define using_fast_io                 \
	ios_base::sync_with_stdio(false); \
	cin.tie(nullptr);                 \
	cout.tie(nullptr);

typedef long long int llint;
typedef unsigned long long int ullint;

llint do_count(int arr[], int lo, int mid, int hi)
{
	int n1 = mid - lo + 1;
	int n2 = hi - mid;

	vector<int> left(n1);
	vector<int> right(n2);

	int idx = lo;

	for (int i = 0; i < n1; i++)
	{
		left[i] = arr[idx];
		idx++;
	}

	for (int i = 0; i < n2; i++)
	{
		right[i] = arr[idx];
		idx++;
	}

	int left_pointer = 0, right_pointer = 0, main_pointer = lo;
	llint inv_cnt = 0;
	while (left_pointer < n1 && right_pointer < n2)
	{
		if (left[left_pointer] <= right[right_pointer])
		{
			arr[main_pointer] = left[left_pointer];
			left_pointer++;
		}
		else
		{
			arr[main_pointer] = right[right_pointer];
			inv_cnt += n1 - left_pointer;
			right_pointer++;
		}
		main_pointer++;
	}

	while (left_pointer < n1)
	{
		arr[main_pointer] = left[left_pointer];
		left_pointer++;
		main_pointer++;
	}

	while (right_pointer < n2)
	{
		arr[main_pointer] = right[right_pointer];
		right_pointer++;
		main_pointer++;
	}

	return inv_cnt;
}

llint inversion_count(int arr[], int lo, int hi)
{
	llint to_return = 0;
	if (lo < hi)
	{
		int mid = lo + (hi - lo) / 2;
		to_return += inversion_count(arr, lo, mid);
		to_return += inversion_count(arr, mid + 1, hi);
		to_return += do_count(arr, lo, mid, hi);
	}
	return to_return;
}

void soln()
{
	// taking an array as input
	int N;
	cin >> N;
	int arr[N];

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	// fetching the inversion count
	llint solution = inversion_count(arr, 0, N - 1);
	cout << solution << endl;
}

int main()
{
	using_fast_io;

	int t = 1;
	// cin >> t;
	while (t--)
	{
		soln();
	}
	return 0;
}