[SDOI2011]染色
简化题意 $:$
给定一棵点带权的树,维护两种操作 $:$
1.把 $(x,y)$ 这条链上的点权全部置为 $w$.
2.查询 $(x,y)$ 这条链上有多少不同的点权.
树剖 $+$ 线段树维护即可.
线段树维护覆盖标记,权值个数和左端点右端点的权值.
向上合并的时候判断,左儿子的右端点权值和右儿子的左端点权值是否相同,如果相同就 $-1$ .
查询的时候,合并左右儿子查询上来的信息时也要类似处理.
这样线段树的问题就解决了.
那么做完了嘛 $?$
没有,你发现树剖跳链的时候也会有合并问题.
那怎么办呢 $?$ 由于树剖跳链是两边跳,所以你需要分别维护每一边的最后一个权值是什么,再下一次跳链的时候判断是否和上一次重复即可.(充分利用树剖 $+$ 线段树的结构性质).
1 |
|