BZOJ1483 [HNOI2009] 梦幻布丁

BZOJ

洛谷

链表+启发式合并

懒得写链表

std::set代替链表

首先算出初始状态答案

然后对于每个修改操作,启发式合并两种颜色。

启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。

简单来说就是弱肉强食。

而且启发式合并的时间复杂度可以证明是O(logn)的

对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。

对于查询操作,由于每次修改同时都计算出答案,直接输出即可。

继续阅读BZOJ1483 [HNOI2009] 梦幻布丁

BZOJ1588 [HNOI2002]营业额统计

BZOJ1588

splay。

把每天的营业额加入splay,查找前驱和后继,统计即可。

注意使用双旋的splay,因为单旋在链状树的情况下时间复杂度会退化。具体证明去问Tarjan。

也可使用其他平衡树或双向链表。双向链表的做法可参考 朱晨光《基本数据结构在信息学竞赛中的应用》。

继续阅读BZOJ1588 [HNOI2002]营业额统计