[Ynoi2018] 未来日记

· · 题解

Description

维护一个数组 a[n]，支持 q 次下面 2 种操作：

$\mathrm{query}(l, r, k)$: 返回 $a[l..r]$ 中的第 $k$ 小值。 #### 限制 $n \leq 10^5 q \leq 10^5 1 \leq a[i], x, y \leq 10^5

Solution

假定 1 \leq a[i], x, y \leq m.

把数组 a 分成大小是 O(\sqrt{n}) 的 O(\sqrt{n}) 块。

用正体 i 表示数组的下标，粗体 \mathbf{i} 表示块的下标。

同时，把值域 [1, m] 分成大小是 O(\sqrt{m}) 的 O(\sqrt{m}).

用粗体 \mathbf{v} 表示 v \in [1, m] 所在的块的编号，即 \mathbf{v} = \lfloor v / \sqrt{m} \rfloor.

令 \mathrm{cnt}[v][\mathbf{i}] 表示在前 \mathbf{i} 个块中，值是 v 的元素个数。

令 \mathrm{blkcnt}[\mathbf{v}][\mathbf{i}] 表示在前 \mathbf{i} 个块中，值在块 \mathbf{v} 中的元素个数。

对于询问 \mathrm{query}(l, r, k), 假定 [l, r] 包含了块 \mathbf{l} 到块 \mathbf{r}, 和另外 O(\sqrt{n}) 个元素 \mathcal{I}.

令 \mathrm{tmpblkcnt}[\mathbf{v}] 表示 \mathcal{I} 中，值在块 \mathbf{v} 中的元素个数。

$$ b(\mathbf{v}) = \mathrm{tmpblkcnt}[\mathbf{v}] + (\mathrm{blkcnt}[\mathbf{v}][\mathbf{r}] -\mathrm{blkcnt}[\mathbf{v}][\mathbf{l} - 1]). $$ 从小到大枚举 $\mathbf{ans}$ 直到 $b(\mathbf{1}) + \dots + b(\mathbf{ans}) \geq k$，得到第 $k$ 小值的块的编号 $\mathbf{ans}$. --- 令 $\mathrm{tmpcnt}[v]$ 表示 $\mathcal{I}$ 中值在块 $\mathbf{ans}$ 中，值是 $v$ 的元素个数。注意 $v$ 的值只有 $O(\sqrt{m})$ 个。 $a[l..r]$ 中，值是 $v$ 的元素数量 $$ c(v) = \mathrm{tmpcnt}[v] + (\mathrm{cnt}[v][\mathbf{r}] -\mathrm{cnt}[v][\mathbf{l} - 1]). $$ 从小到大枚举 $\mathrm{ans}$ 直到总数超过 $k$, 得到第 $k$ 小值 $\mathrm{ans}$. 注意 $\mathrm{tmpblkcnt}[]$ 和 $\mathrm{tmpcnt}[]$ 的大小都是 $O(\sqrt{m})$. 至此，如果维护 $\mathrm{cnt}[][]$ 和 $\mathrm{blkcnt}[][]$, 可以 $O(\sqrt{m})$ 处理 $\mathrm{query}(l, r, k)$. --- 考虑 $\mathrm{change}(l, r, x, y)$. 如果 $\mathcal{I} = \emptyset$, 通过 $\mathrm{cnt}[v][\mathbf{i}] - \mathrm{cnt}[v][\mathbf{i} - 1]$ 得到块 $\mathbf{i}$ 中值为 $v$，可以更新 $\mathrm{cnt}[][]$ 和 $\mathrm{blkcnt}[][]$. 如果 $\mathcal{I} \neq \emptyset$, 需要得到$a[i]$ ($i \in \mathcal{I}$) 的当前值。 --- 为此，对于块 $B$, 维护一个并查集： - $\mathrm{parent}[i]$ 表示 $i$ 在并查集中的父亲，$\mathrm{parent}[i] = i$ 表示 $i$ 是并查集的根； - $\mathrm{value}[i]$ 仅当 $\mathrm{parent}[i] = i$ 时有定义，表示这个集合当前的值。 另外，当 $\mathrm{parent}[i] = i$ 且 $\mathrm{value}[i] = v$ 时，$\mathrm{repr}[v] = i$. --- 当 $\mathrm{change}(\cdot, \cdot, x, y)$ 包含块 $B$ 时， 假设 $x \neq y$ 且值 $\mathrm{repr}[x] = i$ 存在，有两种情况： - 值 $y$ 不存在，那么把 $\mathrm{value}[i]$ 设为 $y$, 同时把 $\mathrm{repr}[y]$ 设为 $i$. - 值 $y$ 存在，那么把 $\mathrm{parent}[i]$ 设为 $\mathrm{repr}[y]$. 时间复杂度 $O(1)$. 当需要得到 $a[i]$ 的当前值时，把 $a[i]$ 设为 $\mathrm{value}[\mathrm{root}(i)]$. 时间复杂度 $O(\sqrt{n})$.