题意

  • 给定n个点对(x,y)，如果不存在一个点对(a,b),使得(a<=x&&b<y)||(a<x&&b<=y),则称(x,y)是有优势的点对
  • 每次加入点对后，输出当前有优势的点对个数

思路

  • 点对问题转换成二维坐标系中问题
  • 画图发现，有优势的点对应的几何意义是，和坐标轴围成的范围(除自身以外的闭集)不含有其他点
  • 用一个容器实现，使该容器对下标进行排序
  • 注意：用map和set都会寄，因为无法处理重复点，本题中，两个重复点会都被记录为有优势点、

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		int n;
		scanf("%d",&n);
		printf("Case #%d:\n",i);
		multiset<pair<int,int>>mp;
		mp.clear();        
		for(int j=0;j<n;j++){
			pair<int,int>a;
			scanf("%d%d",&a.first,&a.second);
			auto pt1=mp.lower_bound(a);
			if(pt1==mp.begin()||a.second<(--pt1)->second){
				mp.insert(a);
				auto pt2=mp.upper_bound(a);
				while(pt2!=mp.end()&&pt2->second>=a.second){
					mp.erase(pt2++);
				}
			}
			printf("%d\n",mp.size());
		}
		printf("\n");
	}
	return 0;
}

STL注意事项

  • map的排序默认按照键升序，可以用greater<>变为降序或者自定义比较函数

map,set,multiset

通用方法

方法 描述
size() 返回元素数量
empty() 判断是否为空
clear() 清空容器
begin()/end() 返回迭代器
rbegin()/rend() 返回反向迭代器
count(value) 统计元素出现次数，可用于判断元素是否出现过

set/multiset 特有方法

方法 描述
insert(value) 插入元素
erase(value) 删除元素
find(value) 查找元素

map 特有方法

方法 描述
operator[] 访问或插入元素
at(key) 安全访问元素
insert({k,v}) 插入键值对
erase(key) 删除键值对

lower_bound和upper_bound

  • lower_bound：返回第一个 不小于 目标 pair 的元素
  • upper_bound：返回第一个 严格大于 目标 pair 的元素
  • upper_bound 会返回严格大，意味着多个元素会先比第一个，如果相同再比较第二个