Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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;
}