题库链接戳这里
E. Excellent Engineers
题意：有n个工程师，取三个技能来衡量工程师的水平。现在给你每个工程师这三个技能在这N人中的排名r1、r2、r3，不存在同名的情况。问：哪些工程师可能是最优秀的？这些可能是最优秀的工程师会出现在候选人名单上，问候选人名单上有多少个人？以数据为例子：
3 | 3
2 3 2 | 1 2 3
3 2 3 | 2 3 1
1 1 1 | 3 1 2
第1组，显然第3人三项技能的排名都是1，故而他是唯一候选人无疑，解为1。第2组里，每个人都有一项技能排名第1，其它虽然排名不及别人，但是不确定在能力上究竟差多少，于是，3个人都有可能是最强的，于是解为3。
这道题挺有意思的。一开始想的是如果工程师A各项技能都强于工程师B，那么建立一条单向边，最后求的是有多少个连通块。但是n范围是1e5，这个复杂度n^2，不可行。解决办法比较巧妙，复杂度是nlogn。
解法思路：先把工程师按r3的情况，从小到大排序。从前到后遍历这个序列，这样会使得对于当前工程师而言，往后的人不会在r3上比自己优秀。在此基础之上，新考虑的人虽然技能3不如前面的人，但是如果技能2是最优秀的，或者说，技能2不是最优秀的，但是技能1，比那些技能2、3都比自己优秀的人优秀，也加入候选人名单。
在技能3有序的情况下，技能1和技能2的分布情况是一个二维图：
中间图的e是新加入的点，虽然因为晚入，技能3略逊，技能1也不是最好的，但是他比技能1比他好的人技能2好，比技能2比他好的人技能1好，故亦入选。我们在下面的算法中，用一个set来维护这样一条链。这条链的意义是：边界。即那些在x或y维度有所突破的人，会成为候选人。为什么一定会成为候选人呢？因为他对于前面的人而言，已经有所突破，他整体实力也许不比前面的人弱，又他比后面的人先考虑，于是技能3强于往后的人，后面的人技能1、2再强，他也可能不比他们弱，于是是否最强不可断定，入候选人集合。
代码里实现稍不一样：先排序r1，然后以r2和r3来模拟上面这样的二维图。之前没接触过这种题(菜)，觉得很巧妙。啰嗦一下，因为名次无同名，所以it1表示的是技能2比E[i]弱的人，it2则表示的是技能比E[i]强的人，要去比较该人和E[i]的技能3情况。
#include <bits/stdc++.h>
using namespace std;
#define lowb lower_bound
const int maxN = 1e5 + 5;
int N, M, K, T;
struct Engineer {
int r1, r2, r3;
Engineer() {}
Engineer(int a, int b, int c)
: r1(a), r2(b), r3(c) {}
};
bool cmp1(Engineer &a, Engineer &b) { return a.r1 < b.r1; }
struct cmp2 {
bool operator() (Engineer a, Engineer b) {
return a.r2 < b.r2;
}
};
Engineer E[maxN];
set<Engineer, cmp2> S;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
for (int i = 0; i < N; ++i)
scanf("%d%d%d", &E[i].r1, &E[i].r2, &E[i].r3);
sort(E, E + N, cmp1);
int ans = 1;
S.clear();
S.insert(E[0]);
set<Engineer>::iterator it, it1, it2;
for (int i = 1; i < N; ++i) {
it1 = S.lowb(E[i]);
it2 = it1;
it2--;
if (it1 == S.begin() || E[i].r3 < it2->r3) {
++ans;
for (it = it1; it != S.end() && E[i].r3 < it->r3;)
S.erase(it++);
S.insert(E[i]);
}
}
printf("%d\n", ans);
}
return 0;
}
