3006번: 터보소트

https://www.acmicpc.net/problem/3006

#include<cstdio>
const int MXN = 1e5;
int ubit[MXN + 1], dbit[MXN + 1], r[MXN], idx[MXN + 1], n;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0, p; i < n; i++) {
        if (i & 1) {
            p = idx[n - i / 2];
            r[i] = n - p;
            for (int j = p; j <= n; j += j&-j) r[i] -= ubit[j];
        }
        else {
            p = idx[i / 2 + 1];
            r[i] = p - 1;
            for (int j = p; j; j -= j&-j) r[i] -= dbit[j];
        }
        for (int j = p; j; j -= j&-j) ubit[j]++;
        for (int j = p; j <= n; j += j&-j) dbit[j]++;
    }
    for (int i = 0; i < n; i++) printf("%d\n", r[i]);
    return 0;
}