예제를 직접 손으로 해보니 은 의 위치가 되는 것 같다. 도 의 위치가 되는 걸까? 우연히도 예제 입력에서 여기까지는 성립한다. 그러나 부터는 통하지 않는데, 본래 수열을 라고 할 때, 은 인데 예제 출력을 보니 에는 이 있다.
이는 에서 보다 왼쪽에 있는게 모두 보다 크다고 생각했기 때문이다.
만약 작은 수부터 순서대로 순회하고, 순회하면서 차례대로 번째 수를 제거한다면 순회중에 번째 수는 언제나 가장 작은 수가 된다. prefix Sum으로 나타내면 자기보다 왼쪽에 있는 수의 개수를 알 수 있지만 update가 있으므로 구간 합 세그먼트 트리를 사용해준다. prefix Sum배열은 단조증가 하므로 이분 탐색이 가능하므로 자기보다 왼쪽에 있는 수의 개수가 개인 지점을 찾아주자.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder bw = new StringBuilder();
int N = Integer.parseInt(br.readLine());
FenwickTree t = new FenwickTree(N);
for (int i = 1; i <= N; i++) t.add(i, 1);
int[] S = new int[N + 1];
for (int i = 1; i <= N; i++) {
int k = t.kth(Integer.parseInt(br.readLine()) + 1);
S[k] = i; t.add(k, -1);
}
for (int i = 1; i <= N; i++) bw.append(S[i]).append("\n");
System.out.print(bw);
}
}
class FenwickTree {
int[] tree;
FenwickTree(int n) { tree = new int[n + 1]; }
void add(int pos, int val) {
while (pos < tree.length) {
tree[pos] += val;
pos += (pos & -pos);
}
}
int sum(int pos) {
int ret = 0;
while (pos > 0) {
ret += tree[pos];
pos -= (pos & -pos);
}
return ret;
}
int kth(int k) {
int lo = 0; int hi = tree.length - 1;
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (mid != 0 && sum(mid) >= k) hi = mid;
else lo = mid;
}
return hi;
}
}