BZOJ 1483 [HNOI2009] 梦幻布丁

发布于 2017-08-13  173 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1483

题意:N 个布丁摆成一行,进行 M 次操作。每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。


做这题收获最大的居然是理解了链表 T.T

从初学一直都是背板子...

对于每种颜色,用链表串起来。两种颜色涂色就是合并两个链表,其实就是将一个链头的 next 设为另一个的 head 这样。

暴力合并是\(O(n)\) 的,启发式合并即可,\(O(nlog_n)\) 的证明比较显然...

 


一个非常弱的准退役OIER