存档

文章标签 ‘线段树’

POJ 2777 Count Color 线段树

2010年10月26日 6 条评论

最近,搞完这个,就复习其他数据结构。这个题想了好久,知道用线段树,却不知道怎么解题。最后看了数据结构书才搞出来。就是给节点设置一个cover域,cover为0代表线段存在多种颜色,非零,代表纯色,数值用于区别颜色种类。
第一次建树时,根节点cover域为1。以后要涂色的时候,先看涂色区域是否覆盖当前节点的范围,如果覆盖,直接更改当前节点的cover域。否则,先看当前节点是否为纯色,如果是纯色,就要把纯色信息传递给左右子树,而当前节点cover域则变为0.表明当前节点覆盖的颜色不在是纯色,这样照着[......]

继续阅读