Luogu5113 Sabbat of the witch

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 维护长为 的序列 ，支持以下三种操作

  • 区间赋值

  • 区间求和

  • 撤回之前的某个区间赋值操作

强制在线，，保证区间赋值不超过 次，时限 。

考虑序列分块。

对于每个元素，用栈维护散块修改。对于每个块，也用栈维护整块修改。链表以时间为序，末端即为最晚的修改。

（为了节省空间，用链表维护栈）

删除时打标记并懒惰删除。

这样，我们容易 查某个位置的值。询问时，只需取出整块的和，对于散块直接暴力。

接下来的任务是维护整块的和。

记块大小为 ，整块的最后修改为 ，且 之后的散块修改个数为 权值为 ，则最终该块的权值和为 。

撤回某个修改时，对于某个块，最后修改时间可能变化，我们要快速求出该块的和。

于是我们对每个元素的 二元组排序，然后二分找出一个后缀。

区间赋值时，整块修改后的和易得。

对于修改中的散块，需要重构。对各个元素的 二元组进行基数排序。

时空复杂度均为 。轻微卡常。