学步园

题目链接：uva 11020 - Efficient Solutions

题目大意：依次给定n个人的坐标，每次输出当前有多少个人属于优势群体，优势群体的定义为不存在另一个人的坐标x，y均小于自己(等于是可以的)

解题思路：用一个set保存当前为优势人群的坐标，每次添加一个人判断是否导致有人失去优势。

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) {
        this->x = x;
        this->y = y;
    }
    bool operator < (const Point& a) const {
        return x < a.x || (x == a.x && y < a.y);
    }
};

multiset<Point> vec;
multiset<Point>::iterator iter;

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        printf("Case #%d:\n", kcas);

        int n, x, y;
        vec.clear();
        scanf("%d", &n);

        while (n--) {
            scanf("%d%d", &x, &y);
            Point p(x, y);
            iter = vec.lower_bound(p);

            if (iter == vec.begin() || (--iter)->y > y) {
                vec.insert(p);
                iter = vec.upper_bound(p);
                while (iter != vec.end() && iter->y >= y)
                    vec.erase(iter++);
            }
            printf("%lu\n", vec.size());
        }

        if (kcas < cas)
            printf("\n");
    }
    return 0;
}