有关MultiSet容器用法

发布时间 2023-10-26 16:35:37作者: DanRan02

基本用法

众所周知,Multiset是一个十分方便的容器,他是不会去重的set集合,而且会将集合内元素自动排序。
其可以支持许多操作。
1.插入操作insert();
2.删除操作erase();
删除操作有两种常用的参数,一种是一个元素类型,会将所有的此类元素删除;而第二种是一个迭代器,会将此迭代器上的元素删除。
3.可以用greater<>重载。
MultiSet默认从小到大进行排序,但是经过重载之后,可以从大到小进行排序。
由于.end()返回的迭代器没有减号重载,可以用greater<>重载之后取.begin()

实战

D. In love
思路:维护最小的右端点和最大的左端点。
策略:如果最大的左端点大于最小的右端点,就存在一对不相交的线段。
代码:

void solve() {

	cin >> n;

	multiset<int, greater<>> l;
	multiset<int> r;
	for (int i = 0; i < n; ++i) {

		char op;
		int l1, r1;

		cin >> op >> l1 >> r1;

		if (op == '+') {
			l.insert(l1);
			r.insert(r1);
		} else {
			l.erase(l.find(l1));
			r.erase(r.find(r1));
		}

		if (l.size() < 2) {
			No;
			continue;
		}

		int rmin = *r.begin();
		int lmax = *l.begin();

		if (rmin < lmax) {
			Yes;
		} else No;
	}

}