我是靠谱客的博主 迅速棒棒糖,最近开发中收集的这篇文章主要介绍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();
}

最后

以上就是迅速棒棒糖为你收集整理的CF773 E - Anonymity Is Important(stl迭代器的各种用法)的全部内容,希望文章能够帮你解决CF773 E - Anonymity Is Important(stl迭代器的各种用法)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(57)

评论列表共有 0 条评论

立即
投稿
返回
顶部