POJ 2777 Count Color 线段树染色

早些日子为了学习线段树,在Du神牛的带领下,做了此题,入门好题也! poj2777 Count Color

此题是本人线段树第二题,前一道是TYVJ1039 忠诚2(一道动态RMQ问题)

输入区间长度L (1 <= L <= 100000),颜色数目 T (1 <= T <= 30) 和 指令数O (1 <= O <= 100000)

接下来O行C x y z 代表将[x,y]区间染成z色,P x y z 代表询问[x,y]有多少种颜色,起始各处颜色为1;

我第一眼看到”1 <= T <= 30″就格外激动为啥不是40呢?显然是为了小于32,所以显然可以用二进制每位表达一种颜色,颜色1是1(0x1)颜色10就是1024(0x400),在线段树里查询便可以获得这一段的几种颜色然后做一次OR操作便可得到所有颜色

我看到T的范围就马上想到到了Matrix67牛的一个位运算优化:位运算简介及实用技巧(二):进阶篇(1)计算二进制中的1的个数的方法

此方法可快速统计int型中1的个数

做这个题的时候曾经碰到个棘手的问题,WA了好几次,后来看了Du神牛的题解 ,发现代码出奇的相似,于是找不同之处,豁然开朗.

错误的代码详见poj2777里Discuss里Comzyh的”Wa的原因

Poj2777 线段树下沉错误
注意这个线段树是用二叉堆方式存储的

这个问题的由来是这样的,架设有一段[1,10]的区间为色,其子树为[1,5],[6,10]我么现在要对[5,7]染成色,怎么做呢?

显然最终情况是[1,4][5,7][7,10]

我的原意是先染色[1,4] 然后染色[7,10] (下沉操作)然后染色[5,7]

后来看了Du神牛的题解,豁然开朗,原来直接将线段下沉到两个子节点即可,即先染色[1,5],在染色[6,10],再染色[5,7],我刚才的做法纯属闲的,我把右边那一段[7,10]染成当前要染的色而不是当前线段的颜色(今天又试了下改正了的,G++688ms,C++516,显然慢).
还是把错误代码贴一下吧,第23行Cover错了.

哎,下面帖下我的G++547ms,C++438ms的代码,初学者,慢没法,另外严重怀疑poj的C++为什么比G++快这么多.

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: POJ 2777 Count Color 线段树染色

2 Responses

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据