Mega Inversions

#include <bits/stdc++.h>

#define ll long long
#define N (1<<19)
using namespace std;

ll v[2 * N];

void inc (int k, ll n) {
    k += N;
    v[k] += n;
    for (k /= 2; k >= 1; k /= 2) v[k] = v[2 * k] + v[2 * k + 1];
}

ll sum (int a) {
    int b = 500000;
    ll s = 0;
    a += N;
    b += N;
    while (a <= b) {
        if (a & 1) s += v[a++];
        if (~b & 1) s += v[b--];
        a /= 2; b /= 2;
    }
    return s;
}

ll v2[2 * N];

void inc2 (int k, ll n) {
    k += N;
    v2[k] += n;
    for (k /= 2; k >= 1; k /= 2) v2[k] = v2[2 * k] + v2[2 * k + 1];
}

ll sum2 (int a) {
    ll s = 0;
    int b = 500000;
    a += N;
    b += N;
    while (a <= b) {
        if (a & 1) s += v2[a++];
        if (~b & 1) s += v2[b--];
        a /= 2; b /= 2;
    }
    return s;
}

int main () {
    int n;
    cin>>n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin>>x;
        ans += sum2(x + 1);
        inc2(x, sum(x + 1));
        inc(x, 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