随笔题解 Pb. 6
我对我暑假期间的摸鱼行为表示沉痛反省。
虽然但是，下次还敢。
有些套路的一道题。但是可以拿来锻炼代码能力。
来源懒得找了。
给出一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。对于所有 $k = 1, 2, \dots, n$，计算以下问题的答案：
- 将序列 $a$ 划分为尽可能少的子区间，使得在每一个子区间内都至多出现 $k$ 个不同的数字。
比如 $a = [1, 5, 7, 8, 1, 7, 6, 1]$，$k = 1, 2, \dots, 8$ 时的答案依次为 $[8, 4, 3, 2, 1, 1, 1, 1]$。具体方案如下：
- $k = 1$：$[[1], [5], [7], [8], [1], [7], [6], [1]]$
- $k = 2$：$[[1, 5], [7, 8], [1, 7], [6, 1]]$
- $k = 3$：$[[1, 5, 7], [8, 1, 7], [6, 1]]$
- $k = 4$：$[[1, 5, 7, 8], [1, 7, 6, 1]]$
- $k \geqslant 5$：$[[1, 5, 7, 8, 1, 7, 6, 1]]$
$1 \leqslant n \leqslant 10^5$。$1 \leqslant a_i \leqslant n$。
$\texttt{2s/256MiB}$。
假设我们确定了一个 $k$ 的值，考虑这样一个简单直接的思路：每次贪心地删去最长的颜色数不超过 $k$ 的前缀。
注意到，对于序列的一个任意的长度为 $k$ 的子区间，它里面的颜色数必定不超过 $k$。即每次删去的前缀长度至少为 $k$。设每次确定前缀长度需要的时间复杂度为 $f(n)$，我们有
于是考虑如何确定前缀长度。做法显然：对于每个位置 $i$，令 $p_i$ 表示 $a_i$ 下一次出现的位置，没有则为 $n + 1$。那么「区间 $[l, r]$ 内的颜色数」就可以转化为「区间 $[l, r]$ 内 $p_i \gt r$ 的 $i$ 的数量」。后者是一个二维数点问题，可以使用主席树求解。
二分一个 $\log$，主席树一个 $\log$，再加上最外层的部分就是 $\Theta(n \log^3 n)$。
很遗憾，这样是无法通过本题的。
平时我们在写线段树的时候，经常会用到线段树上二分的技巧来省去一个 $\log$。但是很遗憾，这种技巧在本题时不适用的。笔者表达能力有限，这部分就留给读者作为习题了。
考虑回顾整道题。现在我们已经将问题转化为了二维数点问题。但是仔细分析发现，我们的标记点只有 $\Theta(n)$ 个，但是询问次数却可以达到 $\Theta(n \log^2 n)$ 次。考虑想办法平衡时间复杂度。
考虑根号算法。将原序列每 $\sqrt n$ 个元素分成一个块。首先维护 cnt1[i][j] 表示前 $i$ 个块里面有多少个数字 $\leqslant j$。
然后考虑散块。注意到块内颜色数必定不会超过 $\sqrt n$，于是考虑块内离散化。即维护 rank[i][j] 表示第 $i$ 个块内 $j$ 的排名（$\lt j$ 的数字的数量 $+1$），cnt2[i][j] 表示 $i$ 这个位置所在的块内，$i$ 本身以及 $i$ 前面的位置里面，有多少个数字块内排名 $\leqslant j$。
上面三个数组的大小均为 $n^{1.5}$。预处理所需要的时间复杂度自然也是 $\Theta(n^{1.5})$。于是总时间复杂度 $\Theta(n^{1.5} + n \log^2 n)$。
还有一点，在本题的数据范围下，一个 $n^{1.5}$ 大小的 int 类型数组需要占用约 $\texttt{120MiB}$ 的内存，所以说三个这样的数组其实是开不下的。但是注意到 rank 和 cnt2 两个数组的值都很小，不会超过 $\sqrt n$。而在本题的数据范围下，后者的极限值约为 $320$。因此可以将这两个数组开成 short 类型。这样就可以通过了。