Luogu4117 [Ynoi2018] 五彩斑斓的世界

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

第二分块。

题意：维护序列 ，支持

  • 把区间 中大于 的数减去

  • 询问 中 的出现次数

允许离线，，时限，空限 。

看起来我们需要一个 时间， 空间的做法。

观察到值域很小，又涉及减和出现次数，做法肯定和值域有关。

先把原序列分块，散块可以暴力，考虑整块如何修改。

批量做估计不行。本题的操作十分特殊，可能可以均摊，我们要想办法构造一个比较紧的解法。

容易发现每个块的最大值不会增大，我们维护块中最大值 。

  • 若 ，则可以忽略。

  • 若 ，被减的数较少，可以暴力修改 中的数(减)。

  • 若 ，被减的数较多，注意到大于 的数减去 小于等于 的数加 ，然后全局减 .

    可以暴力修改 ， 中的数(加)，然后平移值域（指针移动便可）。

我们使用了一点类似启发式合并的思想，每次尽量暴力修改较少的值域范围。

这样的复杂度是啥呢?

不难发现，在 时， 中的数被减一次之后必定小于 ，于是 至多为 。也就是说我们花费 的时间将 减少了 。

在 时，最大值至少减少 。我们花费 的时间将 减少了 。

总而言之，我们花费的时间和 的减少量成正比，而各块的初始 和为 。

上面我们的描述都默认可以任意在值域中取址，如果要做到这一点，必须对每个块都维护一个完整的值域表，空间上无法承受。

然后我们惊觉居然没有强制在线，而且每个块的贡献是独立的，我们对每个块单独计算贡献就能避免同时处理 个值域表了。

还有个问题是，我们有 次散块重构，直接遍历值域表显然是不可行的。

可以使用链表来维护，对每个值维护一个链表维护位置。每次查询的是一个区间的链表头，然后快速地将这些链表连接到指定的链表中。

重构时，可以记录操作中可能出现什么数然后暴力遍历。

为了应付查询，还要维护每个链表的大小。

写起来挺顺的，细节适中，就是要注意数组开多一个块。除掉快读仅有2.3K，良心大分块。