D. In Love-Codeforces Round 905 (Div. 3)

D. In Love

这道题的知识点：
1.multiset
和set不同点在于multiset不去重，可以存放重复元素。
具有自动排序功能
2.迭代器
3.lower_bound()和upper_bound()

只要左端点的最大值大于右端点的最小值就可以存在

两种解题方法，主要就是要做到元素有序高效放置。
1.使用lower_bound()有序插入元素

#include
#include
#include
using namespace std;
int main()
{
    int T;cin>>T;
    vector<int>L,R;
    while(T--){
        char op;
        int l,r;
        cin>>op>>l>>r;
        if(op=='+'){
            L.insert(lower_bound(L.begin(),L.end(),l),l);
            R.insert(lower_bound(R.begin(),R.end(),r),r);
        }else{
            L.erase(find(L.begin(),L.end(),l));
            R.erase(find(R.begin(),R.end(),r));
        }
        if(L.size()&&R.size()&&L.back()>R.front()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.multiset自动排序，这种方法的效率比上面的更高。

#include
#include
using namespace std;
int main()
{
    int T;cin>>T;
    multiset<int>L,R;
    while(T--)
    {
        char op;
        int l,r;
        cin>>op>>l>>r;
        if(op=='+'){
            L.insert(l);
            R.insert(r);
        }else{
            L.erase(L.find(l));
            R.erase(R.find(r));
        }
        if(L.size()&&R.size()&&*L.rbegin()>*R.begin()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23