传送门:点击打开链接
题意:按BST插入节点。最后输出每个节点的父节点的值是多少
思路:这场的cf脑洞都很大。。
首先,假如我们要插入的节点的值为x,我们发现父节点的值一定是<=x的最大值的右节点,或者是>x的最小值的左节点
然后我们还能发现,每次<=x的最大值的右节点,和>x的最小值的左节点,这2个位置,总是只有1个位置已经在之前被放了节点了,总是只有一个位置是空着的
那么x就应该放在这个位置了(@#$%^&*
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;map<int, bool> okl, okr;
int main() {int n, t, v;set<int> S; //FIN;scanf("%d", &n);for(int i = 1; i <= n; i++) {int t, v; scanf("%d", &t);if(i >= 2) {set<int>::iterator it;it = S.lower_bound(t);if(it != S.end() && !okl[*it]) {okl[*it] = 1; v = *it;} else {it = S.upper_bound(t); it--;okr[*it] = 1; v = *it;}printf("%d%c", v, i == n ? '\n' : ' ');}S.insert(t);okl[t] = okr[t] = 0;}return 0;
}