[BZOJ1483/Luogu3201][HNOI2009]梦幻布丁(平衡树,启发式合并)

发布于 2018-02-05  146 次阅读


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

本文链接地址:[BZOJ1483/Luogu3201][HNOI2009]梦幻布丁(平衡树,启发式合并)

Description

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.
例如颜色分别为1,2,2,1的四个布丁一共有3段颜色

Http

BZOJ
Luogu

Tag

平衡树,启发式合并

解决思路

震惊,某选手手写平衡树调一晚上没有调过,一怒之下竟然用\(set\)水过。
对每一种颜色维护一个平衡树存储有那些位置是这个颜色,那么把一种颜色改成另一种颜色的时候,就启发式地把两个合并。全局维护一个答案,若把这个点加入会少一些答案,那么直接减去即可。
但需要注意的是,题中明确说是把\(x\)合并到\(y\),但我们启发式合并的时候可能是把\(y\)合并到\(x\),这时候我们就把\(x\)与\(y\)的编号永久地交换一下,让以后找到\(x\)都相当于找到了\(y\),\(y\)同理。
没错,这一题可以用\(set\)

代码

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

本文链接地址:[BZOJ1483/Luogu3201][HNOI2009]梦幻布丁(平衡树,启发式合并)


HNCJ OIer