CF773 E - Anonymity Is Important（stl迭代器的各种用法）

87 阅读 0 评论 58 点赞

我是靠谱客的博主迅速棒棒糖，这篇文章主要介绍CF773 E - Anonymity Is Important（stl迭代器的各种用法），现在分享给大家，希望可以做个参考。

E - Anonymity Is Important

分析：

区间覆盖，set去重，剔除无效信息
输出有三种情况：
- NO：最好处理，在之前被删除过
- YES：对于当前x，它前面一个，后面一个不与它共有一个有效区间，也就是说x本身有一个有效区间（有效区间是指可能有病人的区间）
- N/A：即其它情况，与其它（前或后）有重合区间
剔除无效信息：对于每一个点，至多两个区间对其有效，一个左一点，一个右一点

复制代码

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N=1e5+5;
set <int> st;
map <int,int> mp;
void solve()
{
    int n,q;
    cin>>n>>q;
    for(int i=0;i<=n+1;i++) st.insert(i);
    while(q--)
    {
        int t,l,r,x;
        scanf("%lld",&t);
        if(!t)
        {
            scanf("%lld%lld%lld",&l,&r,&x);
            if(!x) 
            {
                // 删除 0 的点
                for(auto it=st.lower_bound(l); *it<=r; it=st.lower_bound(l)) st.erase(*it);
            }
            else 
            {
                auto it=mp.lower_bound(l); 
                // 若当前包含x的区间的右端点比r要小，则新的信息是无效的
                if(it!=mp.end() && it->second<=r) continue; 
                mp[l]=r; // 更新
                // 将往前查询包含x的区间，剔除无用的
                for(auto it=mp.find(l);it!=mp.begin() && prev(it)->second>=r; )
                    mp.erase(prev(it)); 
            }
        }
        else 
        {
            scanf("%lld",&x);
            if(!st.count(x)) puts("NO");
            else 
            {
                int l=*prev(st.find(x)), r=*next(st.find(x));
                auto it=mp.upper_bound(l);
                // 检查包含x的区间是否只剩下x一个数
                if(it!=mp.end() && x>=it->first && it->second <r) puts("YES");
                else puts("N/A");
            }
        }
    }
}
signed main()
{
    int T=1;
    //cin>>T;
    while(T--) solve();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N=1e5+5;
set <int> st;
map <int,int> mp;
void solve()
{
    int n,q;
    cin>>n>>q;
    for(int i=0;i<=n+1;i++) st.insert(i);
    while(q--)
    {
        int t,l,r,x;
        scanf("%lld",&t);
        if(!t)
        {
            scanf("%lld%lld%lld",&l,&r,&x);
            if(!x) 
            {
                // 删除 0 的点
                for(auto it=st.lower_bound(l); *it<=r; it=st.lower_bound(l)) st.erase(*it);
            }
            else 
            {
                auto it=mp.lower_bound(l); 
                // 若当前包含x的区间的右端点比r要小，则新的信息是无效的
                if(it!=mp.end() && it->second<=r) continue; 
                mp[l]=r; // 更新
                // 将往前查询包含x的区间，剔除无用的
                for(auto it=mp.find(l);it!=mp.begin() && prev(it)->second>=r; )
                    mp.erase(prev(it)); 
            }
        }
        else 
        {
            scanf("%lld",&x);
            if(!st.count(x)) puts("NO");
            else 
            {
                int l=*prev(st.find(x)), r=*next(st.find(x));
                auto it=mp.upper_bound(l);
                // 检查包含x的区间是否只剩下x一个数
                if(it!=mp.end() && x>=it->first && it->second <r) puts("YES");
                else puts("N/A");
            }
        }
    }
}
signed main()
{
    int T=1;
    //cin>>T;
    while(T--) solve();
}