H1065 [Ynoi2016] 镜中的昆虫

发布于 2021-08-19  1.09k 次阅读


题目链接

题目大意

维护一个长为 $n$ 的序列 $a_i$,有 $m$ 次操作。

  1. 将区间 $[l,~r]$ 的值修改为 $x$。
  2. 询问区间 $[l,~r]$ 出现了多少种不同的数,也就是说同一个数出现多次只算一个。

$1 \le n,~m \le 10^5,~1 \le a_i \le 10^9$

分析

区间数不同颜色数量问题我们常用的解决方案是记 $pre_i$ 等于最大的 $j$ 满足 $j < i$ 且 $a_j = a_i$,数区间内满足 $pre_i < l$ 的数量即为区间内的颜色数量。

此题的难点在于区间修改操作,经分析不难发现当一个区间 $[l,~r]$ 被修改为 $x$ 时 $\forall i \in (l,~r],~pre[i]=i-1$,所以在每次操作后我们只需要:

  1. 将 $pre_l$ 修改为上一个 $x$ 区间的右端点。
  2. 将下一个 $x$ 区间的左端点的 $pre$ 改为 $r$。
  3. 将 $(l,~r]$ 区间内的所有 $pre_i$ 改为 $i-1$。

考虑 3 操作,如果我们在每次修改时将所有 $pre_i \neq i-1$ 的位置找出并修改为 $i-1$,全局花在 3 操作上的修改次数为 $O(n+m)$:初始时每个 $pre_i$ 可能都不等于 $i-1$,而后面的 $m$ 个操作中每个操作最多只会让两个 $pre_i$ 修改得不等于 $i-1$,所以全局出现过 $pre_i$ 不等于 $i-1$ 情况的次数为 $O(n+m)$,所以花在 3 操作上的修改次数也就为 $O(n+m)$。

考虑如何快速找出 $pre_i \neq i-1$ 的位置。容易发现这样的位置一定是一个连续颜色段的开头。因此我们对原序列建一颗 ODT,每次修改 $[l,~r]$ 时,1 操作和 2 操作直接单点修改,3 操作找到 ODT 上被 $[l,~r]$ 包含的所有连续颜色段,将它们全部删除并把它们的左端点的 $pre$ 设为 $i-1$ 即可。

我们可以使用树套树在线维护修改操作并 $O(\log^2 n)$ 解决查询操作。

然后我翻开题解区发现 BFqwq 的题解也使用了树套树,便非常自信地写完了树套树并且提交,不出所料怎么卡空间都是全 MLE。帖子(然后 BF 就在博客的前面加上了“题解不可通过此题,仅供参考”的提示)

考虑使用复杂度不变但空间更小的做法。

我们现在是在使用树套树在线解决带修改二维数点问题,考虑再开一维表示数据修改的时间,问题就转变为静态三维数点问题,离线 CDQ 分治即可。

时间复杂度仍旧为 $O(m \log^2 n)$,空间复杂度优化到 $O(n+m)$。

代码

View on GitHub


我缓慢吐出一串啊吧啊吧并不再想说话