Mega Inversions

#include <bits/stdc++.h>

using namespace std;
struct fenwick{
	vector<int64_t> p;
	int n;
	void init(int n2){
		n = n2;
		p = vector<int64_t>(n+1, 0);
	}

	void add(int idx, int64_t x){
		idx++;
		while(idx <= n){
			p[idx]+=x;
			idx+=idx&(-idx);
		}
	}

	int64_t query(int idx){
		idx++;
		int64_t re = 0;
		while(idx > 0){
			re+=p[idx];
			idx-=idx&(-idx);
		}
		return re;
	}
	int64_t query(int a, int b){
		if(b > 500000 || a > b)
			return 0;
		int64_t re = query(b);
		if(a > 0)
			re-=query(a-1);
		return re;
	}
};
int n;
int a[505050];
int main(){
	cin >> n;
	fenwick t1, t2;
	t1.init(500000);
	t2.init(500000);
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	int64_t ans = 0;
	for(int i = n-1; i >= 0; --i){
		t2.add(a[i], t1.query(1, a[i]-1));
		t1.add(a[i], 1);
		ans+=t2.query(1, a[i]-1);
	}
	cout << ans << endl;
}

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