[백준 1777] 순열복원

문제

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

 

알고리즘

세그먼트 트리

 

풀이

Inversion counting 문제입니다. 각 숫자의 inversion의 개수가 주어졌을 때, 원래 순열을 구하는 문제입니다.

 

예제 입력에서 주어지는 inversion의 개수를 풀어서 설명하자면, 나보다 작은 숫자가 뒤에 몇 개나 있느냐를 의미합니다. 

순열의 총 크기를 안다면, 나보다 작은 숫자가 앞에 몇 개가 있는지 또한 구할 수 있습니다. 이는 $k$번째가 어디에 위치한 지를 묻는 쿼리와 동등합니다. 

 

이때 여러전략을 선택할 수 있지만, 숫자를 올바른 곳에 배치했다면 해당 인덱스를 제외해야 하므로 삭제 연산 또한 가능한 펜윅트리를 사용했습니다. 시간 복잡도는 $O(NlogN*logN)$입니다.

 

코드

#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;
int inv[100001];
int ans[100001];
int fenwick[100001];

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

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

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

    for (int i = N;i >= 1;--i) {
        int idx = i-inv[i];
        int lo = 1;
        int hi = N;
        int best=0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (query(mid) >= idx) {
                best = mid;
                hi = mid - 1;
            }
            else lo = mid + 1;
        }
        ans[best] = i;
        
        update(best, -1);
    }
    REP(i, N) cout << ans[i] << ' ';
    return 0;
}