链表+启发式合并
懒得写链表
std::set代替链表
首先算出初始状态答案
然后对于每个修改操作,启发式合并两种颜色。
启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。
简单来说就是弱肉强食。
而且启发式合并的时间复杂度可以证明是O(logn)的
对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。
对于查询操作,由于每次修改同时都计算出答案,直接输出即可。
链表+启发式合并
懒得写链表
std::set代替链表
首先算出初始状态答案
然后对于每个修改操作,启发式合并两种颜色。
启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。
简单来说就是弱肉强食。
而且启发式合并的时间复杂度可以证明是O(logn)的
对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。
对于查询操作,由于每次修改同时都计算出答案,直接输出即可。
splay。
把每天的营业额加入splay,查找前驱和后继,统计即可。
注意使用双旋的splay,因为单旋在链状树的情况下时间复杂度会退化。具体证明去问Tarjan。
也可使用其他平衡树或双向链表。双向链表的做法可参考 朱晨光《基本数据结构在信息学竞赛中的应用》。