题解 P2486 【[SDOI2011]染色】

2018-10-29 17:02:41


首先这个题肯定要树剖,但是颜色段数不太好维护。

先考虑线段树怎么资瓷这些操作。

线段树要维护该段内的颜色段数、左端颜色、右端颜色。

修改时,打个标记就好了。pushdownpushup应该很容易写。不会的看代码应该就懂了。

至于查询,二分查询左右两端,再加起来。

如果左端的右端点颜色等于右端的左端点颜色,就要-1s

但是如果只查了左边或右边,就不要-1s

再考虑树上怎么资瓷。

先树剖,然后修改还是一样的,一段一段地改。

但是查询就很麻烦,因为还要考虑这一条链和上面一条链交界的地方颜色是否相同。

所以线段树还要资瓷查询区间左右端点颜色的操作。

然后合在一起就好了。

细节见冗长的代码