Luogu4119 [Ynoi2018] 未来日记

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

最初分块。

题意：维护序列 ，支持：

  • 给出 ，将 中的 都替换为
  • 给出 ，查询 中第 小的数。

（视为同阶），时限 ，空限 。

首先来考虑静态的区间 kth 怎么分块。

  • 经典的值域分块：

    类似经典的权值线段树上二分，也有权值块状树组上的 kth。

    记录 表示 有几个，然后对该数组造一棵三层树 ( ) ，在上面爬的复杂度就是。

接下来我们就是要得知一个区间的权值块状树组。

类似主席树的做法，此处可以差分。

给序列分块。我们可以维护前缀块的值域分块，这样差分就能得到完整块的值域分块。

然后 将散块的信息加入即可。

注意，值域分块的外层块只有 的信息，所以写法可以比较暴力。

好现在我们会 的静态区间 kth 了，接着来观察这个 的修改。

显然，其只会更新权值块状树组前缀和中的 个位置，可以直接暴力。

对于散块，可以暴力修改 。

（由于有值域整块前缀和，容易快速判定某个块内是否有 ）

对于整块，若其中无 ，可以忽略。若无 ，可以直接将所有的 修改成 。

若 均有，则直接暴力修改。

  • 分析暴力重构的次数。

    若所有的操作都只涉及整块，某个块内经过 次有效合并必然变为纯色。

    一次合并的代价，块数也均是 ，这部分总复杂度就是 。

    接下来考虑散块重构造成的影响，其可以把块中的一部分 变为 。

    不妨直接视为加入一种新的颜色，则最多导致一次新的合并。

    由于每次只有两个散块重构，最多导致额外的 次合并，复杂度仍然是 。

考虑如何处理 “ 改名为 ” 这一操作，可以搞个数组维护映射。

具体地，为了减小常数，我们维护下列三个值：

  • r1[t][i] 表示块 的第 个编号对应的值。

  • r2[i] 表示整个序列的第 个位置对应的块内编号。

  • tp[t][x] 表示值 在块 中的编号。可以用 short 存储。

时空复杂度均为 。

将值域分块数组的值维度放在前面，这能显著提升空间连续性。

将值域分块的第二层分叉数目置为为 ，这样能利用位运算减小常数。

最后调一个合适的块大小，我选的是 。