基本用法
众所周知,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;
}
}