题解 | #牛可乐与NCPC#
牛可乐与NCPC
https://ac.nowcoder.com/acm/problem/235569
这题好难。。。，题目上要求不存在一个队伍j使得链接：aj≤ai,bj<bi 或者 aj<ai,bj≤bia_j< a_i,b_j\leq b_iaj<ai,bj≤bi 那么就可以加入观察里面。单纯从数据上看两个变量都需要满足，有点麻烦。
但如果放到坐标系上可以看出其实是要求i所形成的矩形里面不能有别的点（包括边框）（这是难想的第一步，将问题进行转换）。那么现在要解决的问题就是如何快速的知道某个矩形里面有没有不符合要求的点。按照题目来说就是每增加一个判断里面是否有点，如果没有就加入观察队列里面，还需要将受这个点影响而导致变成不符合的点排除。
那么如何用代码实现呢，首先加入一个点之后，就得寻找x比他小或者x与之相等但y要比他小的点。因为这些点有可能会导致这个点不是候选点。找到之后如果没有这样的点或者前一个点的y比他要大的话，证明是一个候选点（这里解释下为什么上一个y比他大也可以，因为随着x的增大y应该是减小的，所以只需要判断最后一个x的y比他大，那么前面所有的点的y就都比他大了）。然后就是通过寻找最后一个满足的点，然后判断y是否大于它，如果大于的话就证明得消去了。
小语法：在结构体里面重载运算符<可以改变upper_bound和lower_bound的比较规则。
#include <bits/stdc++.h>
using namespace std;
struct ty{
int x, y;
bool operator < (const ty &a) const {
return x<a.x || (x==a.x&&y<a.y);
}
};
multiset<ty> ms;
int main() {
int T, n;
cin>>T;
for (int i=1;i<=T;i++) {
cin>>n;
ms.clear();
int x, y;
cout<<"Case #"<<i<<":\n";
for (int i=0;i<n;i++) {
scanf("%d%d", &x, &y);
ty p;
p.x = x;
p.y = y;
multiset<ty>::iterator it = ms.lower_bound(p);
if (it==ms.begin()||(--it)->y>y) {
ms.insert(p);
it = ms.upper_bound(p);
while (it!=ms.end()&&it->y>=y) ms.erase(it++);
}
cout<<ms.size()<<endl;
}
cout<<endl;
}
return 0;
}
