[SHOI2009]会场预约 [线段树 染色][STL set]
发布日期:2021-08-10 12:42:04 浏览次数:7 分类:技术文章

本文共 3571 字,大约阅读时间需要 11 分钟。

这个题我xio到了好多东西QAQ

线段树 染色

可以看这个 瓜打了一会儿 发现自己完全不会QAQ 然后学到了线段树染色这一方法

col数组表示这段区间的颜色是否相同 0为不同 1为相同

del记录这种颜色是否被删掉 然后在后面的操作中搞它!

tag记录的区间颜色

QAQ发现我基础真的不牢 啥都没搞清楚:下传操作的进行,是因为当前区间不完全在修改区间范围内((否则就直接changechange并且returnreturn了)

#include
#include
#include
#include
#include
#include
using namespace std;#define Max(x,y) (x)>(y)?(x):(y)#define Min(x,y) (x)>(y)?(y):(x)#define lson o<<1#define rson o<<1|1#define ll long long#define rg registerconst int N=200000+5,M=10000+5,inf=0x3f3f3f3f,P=99999997;int n,cnt=0,tot=0,era,s=inf,t=0;int sum[N<<1],tag[N<<1],col[N<<1],del[N<<1];template
void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x;}struct node{ char a[3]; int x,y;}ask[N];void pushdown(int o,int l,int r){ col[o]=0;//下传时 这个区间显然不同色 if(!tag[o]) return; else tag[lson]=tag[rson]=tag[o],tag[o]=0;}void change(int o,int x,int y,int k){ if(col[o]==1){ //为同一个颜色 if(!del[tag[o]]&&tag[o]) --cnt,++era; //该种颜色未被删掉 del[tag[o]]=1,tag[o]=k;return;//记录为删掉 并改变颜色 } int mid=(x+y)>>1; change(lson,x,mid,k),change(rson,mid+1,y,k); tag[o]=k,col[o]=1;//覆盖 }void buildtree(int o,int l,int r){ col[o]=1;//初始都为一个未被覆盖的颜色 if(l
>1; buildtree(lson,l,mid),buildtree(rson,mid+1,r); }}void update(int o,int l,int r,int x,int y,int k){ if(r
y) return; if(x<=l&&r<=y){ change(o,x,y,k);return; } pushdown(o,l,r);//进行下传操作 因为当前区间不完全在修改区间内 int mid=(l+r)>>1; update(lson,l,mid,x,y,k),update(rson,mid+1,r,x,y,k);}int main(){ freopen("in.txt","r",stdin); rd(n); for(int i=1,x,y;i<=n;++i){ scanf("%s",ask[i].a); if(ask[i].a[0]=='A') rd(x),rd(y),ask[i].x=x,ask[i].y=y,s=Min(s,x),t=Max(t,y); } buildtree(1,s,t); for(int i=1;i<=n;++i) if(ask[i].a[0]=='A'){ ++cnt,era=0; update(1,s,t,ask[i].x,ask[i].y,++tot); printf("%d\n",era); }else printf("%d\n",cnt); return 0;}

STL set

洛谷上一个

用一个结构体来储存预约的方案 我们知道set里不存在相同的key 可以通过s.find()来寻找

通过结构体重载运算符 重载为:bool operator <(const book &b)const{return r<b.l;}

这样a<b即为a完全在b左边 b<a即为a完全在b右边 a==b即为a和b有相交的区间

再来存一下set的用法

begin()       返回set容器的第一个元素

end()        返回set容器的最后一个元素
clear()       删除set容器中的所有的元素
empty()       判断set容器是否为空
max_size()      返回set容器可能包含的元素最大个数
size()        返回当前set容器中的元素个数
rbegin        返回的值和end()相同
rend()        返回的值和rbegin()相同
erase(iterator)   删除定位器iterator指向的值
erase(first,second) 删除定位器first和second之间的值
erase(key_value)  删除键值key_value的值
find()        返回给定值值得定位器,如果没找到则返回end()。
set<int>::iterator iter;

 

#include
using namespace std;#define Max(x,y) (x)>(y)?(x):(y)#define Min(x,y) (x)>(y)?(y):(x)#define ll long long#define rg registerint n;template
void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x;}struct book{ int l,r; bool operator <(const book &b)const{
return r
s;int main(){ freopen("in.txt","r",stdin); rd(n); for(int i=1;i<=n;++i){ char op[2]; scanf("%s",op); if(op[0]=='A'){ int l,r,era=0;rd(l),rd(r); book x=(book){l,r}; set
::iterator iter; iter=s.find(x); while(iter!=s.end()){ ++era;s.erase(iter); iter=s.find(x); } printf("%d\n",era); s.insert(x); } else printf("%d\n",s.size()); } return 0;}

 

转载于:https://www.cnblogs.com/lxyyyy/p/11193738.html

转载地址:https://blog.csdn.net/weixin_30588729/article/details/97865176 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:MySQL在远程访问时非常慢的解决skip-name-resolve
下一篇:解决XMind运行卡顿

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月06日 20时41分00秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

iview 自定义时间选择器组件_Vue.js中使用iView日期选择器并设置开始时间结束时间校验功能... 2021-06-24
java 验证码校验_JavaWeb验证码校验功能代码实例 2021-06-24
java多线程初学者指南_Java多线程初学者指南(4):线程的生命周期 2021-06-24
java进程user是jenkins_java 学习:在java中启动其他应用,由jenkins想到的 2021-06-24
java添加资源文件_如何在eclipse中将资源文件夹添加到我的Java项目中 2021-06-24
java的三种修饰符_3分钟弄明白JAVA三大修饰符 2021-06-24
mysql source skip_redis mysql 中的跳表(skip list) 查找树(btree) 2021-06-24
java sun.org.mozilla_maven编译找不到符号 sun.org.mozilla.javascript.internal 2021-06-24
php curl 输出到文件,PHP 利用CURL(HTTP)实现服务器上传文件至另一服务器 2021-06-24
PHP字符串运算结果,PHP运算符(二)"字符串运算符"实例详解 2021-06-24
PHP实现 bcrypt,如何使php中的bcrypt和Java中的jbcrypt兼容 2021-06-24
php8安全,PHP八大安全函数解析 2021-06-24
php基础语法了解和熟悉的表现,PHP第二课 了解PHP的基本语法以及目录结构 2021-06-24
matlab中lag函数用法,MATLAB movavg函数用法 2021-06-24
matlab变形监测,基于matlab的变形监测数据处理与分析_毕业设计论文 2021-06-24
opencv matlab编程,在Matlab中调用OpenCV函数 | 学步园 2021-06-24
c语言文件wt,c语言,wt和rt中的t是什么意思 2021-06-24
c语言运行几进制,【C语言】求已知等式在几进制条件下成立 2021-06-24
电梯运行仿真c语言代码,电梯调度算法模拟(示例代码) 2021-06-24
android组件动态接收数据库,Android开发——fragment中数据传递与刷新UI(更改控件)... 2021-06-24