[백준 3006] 터보소트

문제

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

 

알고리즘

세그먼트트리

 

풀이

터보소트라는 방법으로 소팅을 할 때, 필요로 하는 교환 횟수를 묻고 있습니다. 일반적인 inversion counting문제는 작은 수부터 inversion들을 세어나가는 문제입니다. 하지만 이 문제에서는 첫 번째로 작은 수, 첫번째로 큰 수, 두 번째로 작은 수, 두번째로 큰 수 와 같이 inversion을 세어나갑니다.

 

다른 여러 문제들에서도 설명드렸지만, 일반적인 방법으로는 $O(N^2)$의 시간 복잡도가 필요하지만 세그먼트 트리를 이용하게 되면 자신보다 앞에 있는 수, 자신보다 뒤에 있는 수들을 한 임의의 수당 $O(logN)$의 시간 복잡도로 해결 가능합니다.

 

펜윅트리에는 쿼리를 진행해야 할 인덱스들을 담아두며, 진행했다면 $update$를 통해 해당 인덱스를 지워줍시다.

 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N,x,p,ans;
int val_idx[100001];
int fen1[100001];

void update(int idx, int val) {
    while (idx <= N) {
        fen1[idx] += val;
        idx += idx & -idx;
    }
}

int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += fen1[idx];
        idx -= idx & -idx;
    }
    return ret;
}

int main() {
    FAST;
    cin >> N;
    REP(i, N) {
        cin >> x;
        val_idx[x] = i;
        update(i, 1);
    }

    REP(i, N) {
        if (i & 1) cout<<query(val_idx[p + 1] - 1), update(val_idx[p + 1], -1);
        else cout<<query(N) - query(val_idx[N - p]), update(val_idx[N - p], -1);

        if (!(i & 1)) ++p;
        cout << '\n';
    }
    return 0;
}