2 seconds
256 megabytes
standard input
standard output
During the programming classes Vasya was assigned a difficult problem. However, he doesn't know how to code and was unable to find the solution in the Internet, so he asks you to help.
You are given a sequence a, consisting of n distinct integers, that is used to construct the binary search tree. Below is the formal description of the construction process.
- First element a1 becomes the root of the tree.
- Elements a2, a3, ..., an are added one by one. To add element ai one needs to traverse the tree starting from the root and using the following rules:
- The pointer to the current node is set to the root.
- If ai is greater than the value in the current node, then its right child becomes the current node. Otherwise, the left child of the current node becomes the new current node.
- If at some point there is no required child, the new node is created, it is assigned value ai and becomes the corresponding child of the current node.
The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the length of the sequence a.
The second line contains n distinct integers ai (1 ≤ ai ≤ 109) — the sequence a itself.
Output n - 1 integers. For all i > 1 print the value written in the node that is the parent of the node with value ai in it.
3
1 2 3
1 2
5
4 2 3 1 6
4 2 2 4
Picture below represents the tree obtained in the first sample.
Picture below represents the tree obtained in the second sample.
题目大意：给你n个不等的数，第一个数字为二叉搜索树的根。然后剩下的n-1个数字依次插入树中，问你各自的父节点是谁。
解题思路：用常规的建树模拟肯定超时。我们知道，如果一个数x要插入树中，如果存在l < x < r，那么我们只需要找到最大的l和最小的r，且他们中之一必是x的父亲。且x要么插在l的右儿子，或者是插到r的左儿子位置。那么只需要再判断一下要插入的位置是否能插，能插即插。同时用map容器模拟树的形态。
收获：知道了set和map是有序的容器。upper_bound(key)返回从容器中找到第一个大于key的记录的迭代器。lower_bound(key)返回从容器中找到第一个大于等于key的记录的迭代器。如果都小于key，那么返回容器的末尾，即container.end()。
#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn = 1e5+200;
const int mod = 1e9+7;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson mid+1,R
set<int>Set;
set<int>::iterator iter;
map<int,int>Lson;
map<int,int>Rson;
int main(){
int n, x;
while(scanf("%d",&n)!=EOF){
scanf("%d",&x);
Set.insert(x);
int ans;
for(int i = 2; i <= n; i++){
scanf("%d",&x);
iter = Set.upper_bound(x);
if(iter!=Set.end() && Lson.count(*iter) == 0){
Lson[*iter] = x;
ans = *iter;
}else{
iter--;
Rson[*iter] = x;
ans = *iter;
}
Set.insert(x);
printf("%d",ans);
if(i == n){
printf("\n");
}else{
printf(" ");
}
}
}
return 0;
}