P14105 [ZJCPC 2017] Heap Partition

一个序列 $S = \{s_1, s_2, \dots, s_n\}$ 被称为 $\textit{heapable}$，如果存在一棵有 $n$ 个节点的二叉树 $T$，使得每个节点恰好用序列 $S$ 中的一个元素进行标记，并且对于每个非根节点 $s_i$ 及其父节点 $s_j$，都满足 $s_j \le s_i$ 且 $j < i$。序列 $S$ 中的每个元素只能用于标记树 $T$ 的某个节点一次。 Chiaki 有一个序列 $a_1, a_2, \dots, a_n$，她想要将其分解为最少数目的可堆子序列（heapable subsequences）。 注意，一个子序列是指可以通过删除一些元素（不改变剩余元素的相对顺序）从原序列得到的序列。

本题有多组测试数据。输入的第一行为整数 $T$，表示测试用例数。对于每一组测试数据： 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^6$。

对于每组测试数据，第一行输出一个整数 $m$，表示分解得到的最少可堆子序列的个数。接下来的 $m$ 行，每行先输出一个整数 $C_i$，表示该子序列的长度。然后在同一行输出 $C_i$ 个递增排列的整数 $P_{i1}, P_{i2}, \dots, P_{iC_i}$，表示该子序列中各元素在原序列中的索引。

由 ChatGPT 5 翻译