关于poj2777这道题目,我会线段树和lazy思想,但不明白用位记录颜色,用或运算合并颜色等是怎么一回事
1个回答
主要就是lazytag这儿嘛.
每个线段树限度节点记录这些信息：sum,p,q,tag,pre,suf
分别表示区间p,q中,有sum个不同的颜色,tag表示lazy标记,-1表示没有标记,其他表示把这个区间染成tag颜色;pre表示这个区间左端点的颜色,suf表示右端点
更新和询问的时候先下传标记.这个不说了,和其他lazy标记一样的
下传标记的时候,直接清空标记,把pre和suf设置为tag的颜色,sum=1,并且把标记给儿子（如果有的话）
然后就是更新节点的操作（记这个节点为u,左儿子为l,右儿子为r）
首先下传来l和r的标记,然后
u.pre = l.pre;
u.suf = r.suf；
u.sum = l.sum + r.sum - (l.suf == r.pre)；
说明一下最后一个
首先把u.sum设为l.sum + r.sum,
但是当左儿子后缀的颜色和右儿子前缀的颜色一样的时候,这两段颜色实际是同一段,我们多算了一次,于是减去
其他的就没什么了吧
