[BZOJ2243/Luogu2486][SDOI2011]染色(树链剖分,线段树)

发布于 2018-04-17  144 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2243/Luogu2486][SDOI2011]染色(树链剖分,线段树)

Description

给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

Tag

树链剖分,线段树

解决思路

将树树链剖分后,考虑用线段树维护连续区间上的颜色段数量,那么合并两个区间时,对结果有影响的即为端点颜色,记录下来合并。在树链剖分跳链的时候,也记录下颜色 。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2243/Luogu2486][SDOI2011]染色(树链剖分,线段树)


HNCJ OIer