自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:04:44，当前版本为作者最后更新于2020-07-21 14:46:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

截至目前（2020.7.21）本题所有题解都是莫队 + 值域分块 / 值域树状数组，但是这道题实际上是有 poly log 解法的

• 分析

  注意到这题是一个带有值域限制的区间数颜色，而区间数颜色是有 poly log 解法的，可以看 这道题 的题解，不过这里还是稍微介绍一下

  那题常数较小 也是唯一能过的 的做法是这样的：

  对于所有询问按右端点 $r$ 排序，然后将 $i$ 从 $1$ 到 $n$ 扫一遍，每次在一个以原数组下标为编号的树状数组上，在 $i$ 的位置加 $1$，在 $[1,i - 1]$ 中最后一个与 $i$ 同色的位置减 $1$，$i$ 移动到 $r$ 时，查 $[l,r]$ 的和就是颜色数

  这实际上是一种 “同色点只数最右边一个” 的思想，每次当 $i$ 出现时，$[1,i - 1]$ 中与 $i$ 同色的点必定不是最右边一个了

  接下来考虑把这个做法搬到这道题上

  实际上并不需要做太大的改动，我们还是可以使用 “同色点只数最右边一个” 的思想，每次在遇到一个新的 $a_i$ 时加入 $a_i$，删去与 $a_i$ 值相同的上一个点

  原来的做法是维护一个只有 (下标) 一维信息的树状数组，改为维护两个信息 (下标,值)，然后每次查询下标在 $[l,r]$ 内，且值在 $[a,b]$ 内有多少个点就可以了

  注意到这题要求线性空间，可以使用 cdq分治 来解决这个问题

  时间复杂度：$O((n + m) \log ^ 2 n)$，空间复杂度：$O(n + m)$

  代码：莫得

  因为这题实在是太卡空间了…… 连空间消耗较小的莫队都是贴着边过的，这个做法的空间消耗肯定更大，八成过不了……