数据结构-BST UVA 11020

查找某一点其左下方没有其他点的点的个数

其实是平衡数的添加删除查找的操作，用系统自带的multiset自动完成该任务

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
typedef long long ll;
struct Point
{
    int a,b;
    bool operator<(const Point &rhs)const
    {
        return a<rhs.a||(a==rhs.a&&b<rhs.b);
    }
};
multiset<Point>S;
multiset<Point>::iterator it;
int main()
{
    int T;
    scanf("%d",&T);
    for(int kase =1;kase<=T;kase++)
    {
        if(kase>1) printf("\n");
        printf("Case #%d:\n",kase);
        int n,a,b;
        scanf("%d",&n);
        S.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            Point p = (Point){a,b};
            it = S.lower_bound(p);  //查找该点应该出现的位置
            if(it==S.begin()||(--it)->b>b)//如果set中没有点，或者前一个点的y值比当前值大，就插入该点
            {
                S.insert(p);
                it = S.upper_bound(p);
                while(it!=S.end() && it->b>=b) //对于所有比插入点大的点，如果他们的y值要比当前的y大，就删去该点
                {
                    S.erase(it++);
                }
            }
            printf("%d\n",S.size());

        }
    }
    return 0;
}