我是靠谱客的博主 迅速棒棒糖,最近开发中收集的这篇文章主要介绍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迭代器的各种用法)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复