题意：
告诉你有n个整数，按顺序构建一棵二叉查找树，既树中每一个节点满足左儿子小于节点，右儿子大于节点。求每次插入一个整数后树中每一个节点深度之和？

思路：
学过二叉查找树的都知道插入操作最坏情况为O(n^2)（链状时），所以模拟肯定过不了。
仔细观察二叉查找树，再分析下插入时进行的操作，我们可以发现对于一个节点，如果它是它父亲的左儿子，则它父亲是整棵树中大于它的最小的节点，如果它是它父亲的右儿子则它父亲是整棵树中小于它的最大的节点，所以你插入一个节点后，它的父节点要么不存在，要么就是小于他的最大节点或大于它的最小节点，那究竟是选哪个做父亲呢，由于在你没插入之前，他们是相邻的，所以他们相连，而你的大小在他们之间，所以你不可能是其中一个的兄弟节点，因此你只能是认最大深度的那个相邻节点为父亲。
发现了这些，你就可以用set容器二分查找相邻节点，用map容器将节点与深度联系。

代码：

#include <bits/stdc++.h>

#define inf 1000000007
#define eps 0.00000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

inline int read()
{
    char c=getchar();
    int f=1, x=0;
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f*x;
}

map<int,int> ma;
set<int> se;
set<int>::iterator it;

int main()
{
    int n;
    scanf("%d",&n);
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        se.insert(x);
        it=se.find(x);
        it++;
        int p1=-1, p2=-1;
        if(it!=se.end())
        {
            p1=ma[*it];
        }
        it--;
        if(it!=se.begin())
        {
            it--;
            p2=ma[*it];
        }
        ma[x]=max(p1,p2)+1;
        ans=ans+ma[x];
        printf("%lld\n",ans);
    }
    return 0;
}