CF1097E Egor and an RPG game

某个星期六下午，Egor 正在玩他最喜欢的 RPG 游戏。在探索新大陆和新领地时，他遇到了如下的标志：  Egor 是一名热情的玩家，同时也是一名算法爱好者。因此他立刻发现了标志上的两个单词中有四个相同的字母——如果我们对第一个单词中的字母 "R"、"E"、"G"、"O" 进行排列，可以得到第二个单词中的字母 "O"、"G"、"R"、"E"。Egor 受到了这个标志的启发，马上想出了一个关于排列的问题。 给定一个长度为 $n$ 的排列。你需要将它划分为若干个非空子序列，使得每个元素恰好属于一个子序列。每个子序列都必须是单调的——即严格递增或严格递减。 如果一个序列可以通过从排列中删除若干（可能为零）元素且不改变剩余元素的顺序得到，则称其为排列的子序列。 子序列的数量需要尽可能少——设 $f(n)$ 为满足任意长度为 $n$ 的排列都可以被划分为不超过 $k$ 个单调子序列的最小整数 $k$。 你需要将给定的排列划分为不超过 $f(n)$ 个单调子序列。

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。 在 hack 时只能使用 $t = 1$。 接下来是 $t$ 组测试用例，每组测试用例如下格式： 每组的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示排列的长度。第二行包含 $n$ 个两两不同的整数 $a_i$（$1 \leq a_i \leq n$），表示排列本身。 所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出如下格式的答案： 第一行输出 $k$（$1 \leq k \leq f(n)$），表示划分得到的子序列数量。接下来的 $k$ 行，每行描述一个子序列。每个描述以一个整数 $l_i$（$1 \leq l_i \leq n$）开头，表示该子序列的长度，后跟 $l_i$ 个整数，表示该子序列在排列中出现的顺序。 你输出的每个子序列必须是严格递增或严格递减的。 如果有多种划分方案，输出任意一种均可。

在样例中，可以将： - $[4, 3, 1, 2]$ 划分为 $[4, 3, 1]$、$[2]$ - $[4, 5, 6, 1, 3, 2]$ 划分为 $[4, 1]$、$[5, 6]$ 和 $[3, 2]$ - $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ 划分为 $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ 当然，还存在许多其他的划分方案。 由 ChatGPT 4.1 翻译