P9kshp - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define endl "\n"
#define int long long
#define double long double
#define __builtin_popcount __builtin_popcountll
#define join(z, x, y); merge(begin(x), end(x), begin(y), end(y), back_inserter(z));
#define FastIO(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int MAXN = 300003;
const int BASE1 = 311;
const int BASE2 = 997;
const int INF = (int)1e18;

int n, a[MAXN], seg[4 * MAXN];

void update(int i, int l, int r, int pos){
    if(l == r){
        seg[i] += 1;
    }
    else{
        int m = l + r >> 1;
        if(pos <= m){
            update(2 * i, l, m, pos);
        }
        else{
            update(2 * i + 1, m + 1, r, pos);
        }
        seg[i] = seg[2 * i] + seg[2 * i + 1];
    }
}

int get(int i, int l, int r, int u, int v){
    if(u > r || v < l) return 0;
    if(u <= l && r <= v) return seg[i];
    int m = l + r >> 1;
    return get(2 * i, l, m, u, v) + get(2 * i + 1, m + 1, r, u, v);
}

signed main() {
    FastIO();
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        cnt += get(1, 0, n - 1, a[i] + 1, n - 1);
        update(1, 0, n - 1, a[i]);
    }
    cout << cnt << endl;
    for(int i = 0; i < n - 1; i++){
        cnt += n - 1 - 2 * a[i];
        cout << cnt << endl;
    }
    return (0 ^ 0);
}