Problem I
Efficient Solutions
Input: Standard Input

Output: Standard Output

J.Michael Straczynski, "The Deconstruction ofFalling Stars."

The princess of Centauri Prime isthe galaxy's most eligible bachelorette of the year.She has hopeful grooms lined up in front of the royal palace for a chance tospend 5 minutes to try and impress her. After 5 minutes, the gentleman iscarried out of the royal chambers by the palace guards, and the princess makesa decision. She rates the lad on his lineage and charm by giving him a scorefor each of the two properties. On Centauri Prime, low scores are better thanhigh scores.

Suppose that she observes twogentlemen - A and B. She assigns A the scores L_A and C_A(for lineage and charm, respectively). B receives scores L_B and C_B.Then A is dominated by B if either

• L_B < L_A and C_B <= C_A, or
• L_B <= L_A and C_B < C_A.

In other words, if at least oneof B's scores is better than A's, and the other score is not worse. Sheconsiders a gentleman to be efficient (or Pareto-optimal) if she has notyet met any other gentleman who dominates him. She maintains a list of efficient grooms and updates itafter each 5-minute presentation.

Given the queue of bachelors andthe scores assigned to them by the princess, determine the number of entries inthe list of efficient grooms aftereach performance.

Input
The first line of input gives the number ofcases, N (0<N<40). N test cases follow.

Each one starts with a linecontaining n (0≤n≤15000) - the size of the queue. Thenext n lines will each contain two scores (integers in the range [0, 10⁹]).Initially, the list is empty.

Output
For each test case, output one line containing "Case #x:"followed by n lines, line i containing thesize of the list of efficient groomsafter the i^th update. Print an empty linebetween test cases.

4

1

100 200

2

100 200

101 202

2

100 200

200 100

5

11 20

20 10

20 10

100 20

1 1

Case #1:

1

Case #2:

1

1

Case #3:

1

2

Case #4:

1

2

3

3

1

Problemsetter: Igor Naverniouk
Special Thanks: Yury Kholondyrev

Warming: The judge input file size is about 1.2 MB.

題目描述：
有兩種屬性血統跟魅力，這個支配的方式比較特別，數值小的會支配大的，因此跟常見的支配點定義不同，題目要求逐步放入新的點，詢問當前支配點的個數。

題目解法：

由於圖形要維護一個凹口，又由於可以重複計算同一個點，在此使用 multiset 的有序性，
當給予的點會變成一個新的支配點時，往 x 較大的方向掃描，將被支配的點從支配點集中剔除。

利用 multiset 操作都可以在 O(logn) 內完成，而每個點出入點集一次，因此可以在 O(nlogn) 內完成。

#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a, int b):
        x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
int main() {
    int testcase, cases = 0;
    int n, x, y;
    int i, j;
    scanf("%d", &testcase);
    while(testcase--) {
        printf("Case #%d:\n", ++cases);
        scanf("%d", &n);
        multiset<Pt> S;
        multiset<Pt>::iterator it;
        for(i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            Pt p(x, y);
            it = S.lower_bound(p);
            if(it == S.begin() || (--it)->y > y) {
                S.insert(p);
                it = S.upper_bound(p);
                while(it != S.end() && it->y >= y)
                    S.erase(it++);
            }
            printf("%d\n", S.size());
        }
        if(testcase)
            puts("");
    }
    return 0;
}