1849번: 순열

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


$O(n\lg n)$

순서대로 남은 x+1번째 idx를 구한다. 이는 bit나 세그먼트 트리 등을 사용해 해결할 수 있다.

#include<cstdio>
const int MXN = 1e5;
int n, t[MXN * 4], a[MXN];
int kth(int h, int l, int r, int x) {
    t[h]++;
    if (l == r) return l;
    int m = (l + r) / 2;
    return x <= m - l + 1 - t[h * 2 + 1] ? kth(h * 2 + 1, l, m, x) :
        kth(h * 2 + 2, m + 1, r, x + t[h * 2 + 1] - m + l - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), a[kth(0, 0, n - 1, x + 1)] = i;
    for (int i = 0; i < n; i++) printf("%d\n", a[i]);
    return 0;
}