백준 3006

 

3006번: 터보소트

 

풀이

  각 숫자가 어느 자리에 있는지 먼저 기록한다. 숫자 i를 정렬할 때 맨 앞이나 맨 뒤로 보내 정렬하므로 숫자 i가 있는 위치와 가야되는 위치 사이에 있는 숫자의 개수를 파악하면 된다. 그리고 정렬된 숫자를 제외하고 같은 작업을 반복하면 된다. 1을 맨 앞, n을 맨 뒤로 추상화할 수 있다.

 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int tree[1 << 20];
int base, n;
vector<int> a;

int sum(int a, int b) {
    a += base; b += base;
    int res = 0;
    while (a <= b) {
        if (a % 2 == 1) res += tree[a++];
        if (b % 2 == 0) res += tree[b--];
        a /= 2; b /= 2;
    }
    return res;
}

void erase(int k) {
    k += base;
    tree[k] = 0;
    for (k /= 2; k > 0; k /= 2) {
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for (base = 1; base < n + 1; base *= 2);
    a = vector<int>(n + 1);
    for (int i = 1; i <= n; i++) {
        int t; cin >> t;
        a[t] = i;
    }
    for (int i = base + 1; i < base + n + 1; i++) {
        tree[i] = 1;
    }
    for (int i = base - 1; i > 0; i--) {
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1) {
            int t = (i + 1) / 2;
            int pos = a[t];
            erase(pos);
            cout << sum(1, pos - 1) << '\n';
        }
        else {
            int t = n - (i - 1) / 2;
            int pos = a[t];
            erase(pos);
            cout << sum (pos + 1, n) << '\n';
        }
    }
    return 0;
}