Inversion count is the number of index $$$i$$$ and $$$j$$$ that sastifies:

• $$$i \lt j$$$

• $$$a_i \gt a_j$$$

For example, you were given this array: $$$1, 5, 2, 4, 3$$$. This array has 4 inversions, with index: $$$(2, 3), (2, 4), (2, 5), (4, 5)$$$. $$$(2, 3)$$$ is an inversion, since $$$2 \lt 3$$$ and $$$a_2 = 5 \lt a_3 = 2$$$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 69;
int a[N]; //the given array
long long cnt; //The number of inversions. Use long long to avoid overflow

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) {
	    for (int j = i + 1; j <= n; j ++) {
	        //by writing the for loop like this, the first condition (i < j) is already satisfied. Now, we 
	        //just need to check the second condtion (a_i > a_j)
	        if (a[i] > a[j]) {
	            cnt ++;
	        }
	    }
	}
	cout << cnt;
}

Merge sort is a sorting algorithm. How it works is simple:

Let split array $$$a$$$ into 2 halves: array $$$b$$$ and $$$c$$$. Assume that you can sort the array $$$b$$$ and $$$c$$$. Then, to sort array $$$a$$$, you just simply need to merge array $$$b$$$ with $$$c$$$ using two pointers. Now, the array $$$a$$$ is sorted. To sort array $$$b$$$ and $$$c$$$, do the same thing again: split the array $$$b$$$ into $$$b1$$$ and $$$b2$$$, sort them, then merge them. Do this until the base case, where the length of the array is 1, you get the merge sort algorithm.

Time complexity: $$$O(n$$$ $$$log$$$ $$$n)$$$

Maybe count this when you merge the 2 arrays.

Remember when you merge 2 sorted arrays using two pointers? To do this, you iterate pointer $$$i$$$ through the array $$$b$$$, pointer $$$j$$$ through the array $$$c$$$, and add the smaller one to the answer array. So, what if $$$b_i \gt c_j$$$? (In other word, what do you do when $$$a_i \gt a_j$$$?)

Read the hint. If $$$b_i \gt c_j$$$, you increase the cross inversions count by one. So, now, you get the inversion count of array $$$a$$$ by take the sum of the inversion count in array $$$b$$$, $$$c$$$, and the cross inversions. To find the number of inversions in array $$$b$$$, you do the same thing: split the array $$$b$$$ into two halves $$$b1$$$ and $$$b2$$$, then count the inversion of array $$$b1$$$ and $$$b2$$$ using the same method, as well as the cross inversions of $$$b1$$$ and $$$b2$$$. Problem solved!

#include <bits/stdc++.h>
using namespace std;

//this code is made by a human, not AI. The comments and long function name is to make the code easier to understand
//sometimes I regret making long function name -_-

const int N = 1e5 + 69;
vector <long long> a; //the given array
int n;

long long count_cross_inversion(vector <long long> &a, int l, int mid, int r) {
    vector <long long> b, c; //array b and c
    b.push_back(0);
    c.push_back(0); //push_back to make them 1-index
    for (int i = l; i <= mid; i ++) {
        b.push_back(a[i]);
    }
    for (int i = mid + 1; i <= r; i ++) {
        c.push_back(a[i]);
    }
    //making array b and c
    int l1 = mid - l + 1;
    int l2 = r - mid; //the length of array b and c
    int i = 1;
    int j = 1; //the two pointers
    int idx = l; //the current index of array a
    long long ans = 0;
    while (i <= l1 && j <= l2) {
        if (b[i] <= c[j]) { //normal case
            a[idx] = b[i];
            i ++;
        } else if (b[i] > c[j]) {
            //this is the case where b[i] > c[j] and i < j; aka the case where there's an inversion
            a[idx] = c[j];
            ans += (l1 - i + 1); //we add l1 - i + 1, because if b[i] > c[j] then b[i + 1] > c[j], ..., b[l1] > c[j] (since the array b is sorted)
            j ++;
        }
        idx ++;
    }
    //add remaining numbers, as usual
    while (i <= l1) {
        a[idx] = b[i];
        idx ++;
        i ++;
    }
    while (j <= l2) {
        a[idx] = c[j];
        idx ++;
        j ++;
    }
    return ans;
}

long long count_inversion(vector <long long> &a, int l, int r) { //count the number of inversions of array a in the range l and r
    if (l == r) { //base case, where the length of a is 1. The answer for this case is 0
        return 0;
    }
    int mid = (l + r) / 2; //mid is the midpoint of the array, to split the array a into array b and c.
    long long res = 0;
    res += count_inversion(a, l, mid); //count the number of inversions in range l and mid (aka in array b, as well as sort the array b)
    res += count_inversion(a, mid + 1, r); //same thing for array c
    res += count_cross_inversion(a, l, mid, r);
    return res;
}

int main() {
	cin >> n;
	a.push_back(0); //push back to make the vector 1-index
	for (int i = 1; i <= n; i ++) {
	    int x; cin >> x;
	    a.push_back(x);
	}
	cout << count_inversion(a, 1, n);
}

#include <bits/stdc++.h>
using namespace std;

//this code is made by a human, not AI. The comments and long function name is to make the code easier to understand
//sometimes I regret making long function name -_-

const int N = 1e6 + 69;
long long fenwick_tree[N];
int n;
 
long long get(int i) {
    int idx = i;
    long long ans = 0;
    while (idx) {
        ans += fenwick_tree[idx];
        idx -= idx & (-idx);
    }
    return ans;
}
 
void update(int u) { //increase the element of freq[u] by 1
    int idx = u;
    while (idx <= N) {
        fenwick_tree[idx] ++;
        idx += idx & (-idx);
    }
}

//the whole thing above is the template for fenwick tree

int main() {
	cin >> n;
    vector <long long> a;
	a.push_back(0); //push back to make the vector 1-index
	for (int i = 1; i <= n; i ++) {
	    int x; cin >> x;
	    a.push_back(x);
	}
    long long count_inversion = 0;
	for (int i = n; i >= 1; i--) { //iterate i from back to front
        count_inversion += get(a[i] - 1); //add the answer by prefix[a[i] - 1]
        update(a[i]); //update the fenwick tree
    }
    cout << count_inversion;
}

Use integer compression!

If you didn't know, you can compress integers into smaller ones if the problem only require the less than, equal or larger than in value. The inversion count is in this type too!

For example, you were given an array $$$a = {123, 783274, 1037, 19472, 21}$$$. The inversion count of this array is 6. You can compress this array into $$${2, 5, 3, 4, 1}$$$ without changing the inversion count.

#include <bits/stdc++.h>
using namespace std;

//this code is made by a human, not AI. The comments and long function name is to make the code easier to understand
//sometimes I regret making long function name -_-

const int N = 1e6 + 69;
long long fenwick_tree[N];
map <long long, int> m;
int n;
 
long long get(int i) {
    int idx = i;
    long long ans = 0;
    while (idx) {
        ans += fenwick_tree[idx];
        idx -= idx & (-idx);
    }
    return ans;
}
 
void update(int u) { //increase the element of freq[u] by 1
    int idx = u;
    while (idx <= N) {
        fenwick_tree[idx] ++;
        idx += idx & (-idx);
    }
}

//the whole thing above is the template for fenwick tree

int main() {
	cin >> n;
    vector <long long> a;
    set <long long> s; //add to a set to sort the numbers, as well as only store elements that aren't the same
	a.push_back(0); //push back to make the vector 1-index
	for (int i = 1; i <= n; i ++) {
	    int x; cin >> x;
	    a.push_back(x);
        s.insert(x);
	}
    int idx = 1; // the current number
    for (long long i : s) {
        m[i] = idx; //use map to remember what is the compressed number of an elements
        idx ++;
    }
    for (int i = 1; i <= n; i ++) {
        a[i] = m[a[i]]; //compress the numbers
    }
    //the rest is exactly the same
    long long count_inversion = 0;
	for (int i = n; i >= 1; i--) { //iterate i from back to front
        count_inversion += get(a[i] - 1); //add the answer by prefix[a[i] - 1]
        update(a[i]); //update the fenwick tree
    }
    cout << count_inversion;
}