문제

• 
• 시간 제한: 0.5초
• 메모리 제한: 512MB

Problem Analysis

이처럼, a[i] 만큼 앞에 빈칸을 둔 자리에 i를 배치하면, 문제를 해결할 수 있다. 이때 빈칸을 Naive 하게 세면 O(N^2)이 걸린다. 이를 개선하기 위해, Segment Tree를 이용하면, 구간의 크기를 쉽게 구할 수 있다.

Algorithm

순열의 각 범위에 존재하는 빈칸의 수를 Segment Tree 에 저장하여, 다음을 반복한다.

1. A[i] 개의 빈칸을 가지는 순열의 가장 오른쪽 위치를 찾아, i를 해당 위치에 배치한다.
2. 해당 위치에 대해 ST에서 -1한다.

Data Structure

• ST[]: 순열의 각 범위에 존재하는 빈칸의 수를 저장하는 Segment Tree

결과

Other

시간 복잡도는 O(NlogN)이다.