Mega Inversions

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

const int N = 5 * (1e5);
int vals [N];
long long count [N+2];
long long total [N+2];

void add_total(int i, long long v) {
	while(i < N+2) {
		total[i] += v;
		i += (i & -i);
	}
}
long long count_total(int i) {
	long long res = 0;
	while(i > 0) {
		res += total[i];
		i -= (i & -i);
	}
	return res;
}
void add_count(int i, long long v) {
	while(i < N+2) {
		count[i] += v;
		i += (i & -i);
	}
}
long long count_count(int i) {
	long long res = 0;
	while(i > 0) {
		res += count[i];
		i -= (i & -i);
	}
	return res;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	for (int i = 0; i < n; ++i) {
		std::cin >> vals[i];
	}
	long long res = 0;
	for (int i = n-1; i >= 0; --i) {
		res += count_total(vals[i] - 1); // all three
		add_total(vals[i], count_count(vals[i] - 1)); // two
		add_count(vals[i], 1); // one
	}
	std::cout << res << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED