看到这道题的时候,最先想到的就是模拟,然后想了下单链会T,于是想到了,对于二叉搜索树来说,他每个点都管辖着一段数值区间 $[l,r]$,当有某个数再这个数值区间以内时,那个数就会落在这个点所在的子树下,因此考虑维护区间信息。可以用线段树去维护,也可以使用 $ODT$ 。这里代码使用 $ODT$,因为每次插入节点相当于将一段区间推平成某个数,这就是 $ODT$ 的基础操作
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
map<int,int> M ;
int par[maxn] ;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1 ;
// cin >> T ;
rep(test,1,T + 1){
int n ;
cin >> n ;
M[1] = 0 ;
rep(i,1,n + 1) {
int t;
cin >> t;
auto it = --M.upper_bound(t) ;
par[t] = it->second ;
it->second = t;
if (!M.count(t + 1))
M[t + 1] = t ;
}
rep(i,1,n + 1) cout << par[i] << ' ' ;
}
return 0;
}