Rinne Loves Data Structure

题目描述

Rinne 喜欢 OI。在 9102 年的 PION 中，她在初赛遇到了这样一道题目：
阅读下列代码，然后回答问题。

补充：建树过程中会更新lc和rc，这实质上是一个二叉查找树的插入过程。
定义一个玄学节点叫做 R，每次操作读入 val ，执行 Insert(R,val)。
问题：每次 Insert 操作结束之后，输出当前节点的深度和。
这里我们定义 R 节点的深度为 0。

输入描述:

第一行一个整数 N，表示操作次数。
接下来 N 行，第 i 行有一个值 ，表示第 i 次操作的 。

输出描述:

N 行，每行输出该次操作完后的答案。

题解

题目中代码所建出来的二叉树一个节点的左子树上的值都小于该节点，右子树上的值都大于该节点
如果我们直接按题干模拟的话，会毫不意外的T掉，在最坏的情况下，这棵树会退化成一条链，复杂度会变成。
插入的点可能是作为左儿子也可能是作为了右儿子。那么他的前驱节点就是可能比他大或者比他小。那么我们每次就找到第一个比要插入的值大的点和第一个比当前值要小的点，看看这两个哪个深度比较深即为他要插入的位置。
为什么要选择深度比较深的那个点呢？如果我们把它插到了深度较浅的那个点上的话，那个节点就会多出一支子树，就不符合二叉树的要求了。
我们可以用set来维护当前插入的值，再开一个容器记录每个值的深度，每次找与插入值相邻的两个点，取他们较深的一个就好啦。

代码

/*
* Coder: niiii
* Language: cpp
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+100;
const int mod=1e9+7;
ll ans=0;
set<int> st;
unordered_map<int,int> mp;
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        int val;
        cin>>val;
        if(i){
            auto it=st.lower_bound(val);
            if(it==st.begin()){
                mp[val]=mp[*it]+1;
            }
            else if(it==st.end()){
                mp[val]=mp[*prev(it)]+1;
            }
            else {
                mp[val]=max(mp[*prev(it)],mp[*it])+1;
            }
        } else{
            mp[val]=0;
        }
        //cout<<"***"<<mp[val]<<endl;
        st.insert(val);
        ans+=mp[val];
        cout<<ans<<endl;
    }
}