레이팅 미적용설명
이진 탐색 트리는 모든 노드가 자식 노드를 최대 두 개(왼쪽 자식과 오른쪽 자식) 가지는 트리이다. 각 노드에는 정수가 하나씩 적혀 있다. 어떤 노드에 수 \(X\)가 적혀 있다면, 그 노드의 왼쪽 서브트리의 수들은 \(X\)보다 작고 오른쪽 서브트리의 수들은 \(X\)보다 크다.
\(1\) 이상 \(N\) 이하의 정수들로 이루어진 수열이 주어지는데, 각 수는 수열에 정확히 한 번씩 나타난다. 이 수열로 이진 탐색 트리를 만들어야 한다. 첫 번째 수를 루트 노드에 넣고, 나머지 수를 순서대로 삽입한다. 다시 말해, 나머지 각 수에 대해 insert(X, root)를 실행한다:
insert(number X, node N)
increase the counter C by 1
if X is less than the number in node N
if N has no left child
create a new node with the number X and set it to be the left child of node N
else
insert(X, left child of node N)
else (X is greater than the number in node N)
if N has no right child
create a new node with the number X and set it to be the right child of node N
else
insert(X, right child of node N)
각 수가 삽입될 때마다 카운터 \(C\)의 값을 계산하는 프로그램을 작성하시오. 카운터의 초깃값은 \(0\)이다.
제약
입력 형식
첫째 줄에 수열의 길이인 정수 \(N\) (\(1 \le N \le 300\,000\))이 주어진다.
다음 \(N\)개의 줄에 수열의 수들이 주어진다. 구간 \([1, N]\)에 속하는 정수이며, 서로 다르다.
출력 형식
\(N\)개의 정수를 한 줄에 하나씩 출력한다. 각 수가 트리에 삽입된 뒤의 카운터 \(C\)의 값이다.
채점: 전체 점수의 \(50\%\)에 해당하는 테스트 케이스에서는 \(N\)이 최대 \(1000\)이다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 120점 |
예제 1
입력
4
1
2
3
4출력
0
1
3
6예제 2
입력
5
3
2
4
1
5출력
0
1
2
4
6예제 3
입력
8
3
5
1
6
8
7
2
4출력
0
1
2
4
7
11
13
15문제 정보
태그