백준 1777 - 순열 복원

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

 

ICPC 문제 Permutation Recovery와 거의 비슷한 문제이며 하이퍼링크에서 풀이를 확인할 수 있다.

 

다만 이 문제는 위와는 다르게 i 이전의 index에서 자기보다 큰 숫자를 세는 것이 아니라 i 이후의 index에서 자기보다 큰 숫자를 세는 것이다.

 

입력으로 들어온 수열을 거꾸로 하여 위와 같은 풀이를 적용하면 해결할 수 있다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int seq[100001];
int ar[100001];

inline int mid(int stt, int end) { return stt + (end - stt) / 2; }

int init(vector<int> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = 1;
    int m = mid(start, end);
    return tree[node] = init(tree, node * 2, start, m) + init(tree, node * 2 + 1, m + 1, end);
}

void update(vector<int> &tree, int node, int start, int end, int idx, int diff)
{
    if (idx < start || idx > end) return;

    tree[node] += diff;

    if (start != end)
    {
        int m = mid(start, end);
        update(tree, node * 2, start, m, idx, diff);
        update(tree, node * 2 + 1, m + 1, end, idx, diff);
    }
}

int query(vector<int> &tree, int node, int start, int end, int kth)
{
    if (start == end) return start;
    int m = mid(start, end);
    int stack_left = tree[node * 2];

    if (stack_left > kth) return query(tree, node * 2, start, m, kth);
    return query(tree, node * 2 + 1, m + 1, end, kth - stack_left);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> seq[i];

    vector<int> segtree(n * 4);
    init(segtree, 1, 1, n);
    
    for (int i = n; i > 0; --i)
    {
        int val = query(segtree, 1, 1, n, seq[i]);
        ar[val] = i;
        update(segtree, 1, 1, n, val, -1);
    }

    for (int i = n; i > 0; --i)
        cout << ar[i] << ' ';
}