Mega Inversions

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1<<20;
ll st[2*N];
ll st2[2*N];
ll getSum(int a, int b ){
	a += N;
	b += N;
	ll sum = 0;
	for(; a <= b; a/=2, b/=2) {
		if(a&1) sum += st[a++];
		if(~b&1) sum += st[b--];
	}
	return sum;

}
void setValue(int a, ll v) {
	a += N;
	st[a] += v;
	for(a/=2; a; a/=2) {
		st[a] = st[a*2] + st[a*2+1];
	}
}
ll getSum2(int a, int b ){
	a += N;
	b += N;
	ll sum = 0;
	for(; a <= b; a/=2, b/=2) {
		if(a&1) sum += st2[a++];
		if(~b&1) sum += st2[b--];
	}
	return sum;

}
void setValue2(int a, ll v) {
	a += N;
	st2[a] += v;
	for(a/=2; a; a/=2) {
		st2[a] = st2[a*2] + st2[a*2+1];
	}
}
int t[1010101];
int main() {
	int n;
	cin>>n;
	ll ans = 0;
	for(int i = 0; i < n; ++i) {
		cin>>t[i];
		ans += getSum(t[i]+1, N-1);
		setValue(t[i], getSum2(t[i]+1, N-1));
		setValue2(t[i], 1);
	}
	cout<<ans<<'\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