← 返回题目列表

Codeforces · 1097/E

E. 叶戈尔和一款 RPG 游戏

中文机器翻译题面 查看原题

一个星期六的下午,Egor 正在玩他最喜欢的 RPG 游戏。在发现新的土地和领土时,他发现了以下标志:

Egor 是一位充满激情的玩家,但他也是一位算法家。这就是为什么他立即在上面的标牌上的两个单词中发现了四个常见字母——如果我们从第一个单词中排列字母“R”、“E”、“G”、“O”,我们就可以得到字母“O”、“G”、“R”、“E”。叶戈尔受到这个符号的启发,立即想出了一个关于排列的问题。

给你一个长度为 $$$n$$$ 的排列。您必须将其拆分为一些非空子序列,以便排列的每个元素恰好属于一个子序列。每个子序列必须是单调的,即要么递增,要么递减。

如果序列可以通过删除一些(可能没有)元素而从排列中导出,而不改变剩余元素的顺序,则该序列称为子序列。

子序列的数量应该足够小——令 $$$f(n)$$$ 为最小整数 $$$k$$$,这样长度为 $$$n$$$ 的每个排列最多可以划分为 $$$k$$$ 个单调子序列。

您需要将排列拆分为最多 $$$f(n)$$$ 单调子序列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。

你只能在 hacks 中使用 $$$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$$$ 整数 - 该子序列的值按照它们在排列中出现的顺序排列。

您输出的每个子序列必须是递增或递减。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

3
4
4 3 1 2
6
4 5 6 1 3 2
10
1 2 3 4 5 6 7 8 9 10

输出 #1

2
3 4 3 1
1 2
3
2 4 1
2 5 6
2 3 2
1
10 1 2 3 4 5 6 7 8 9 10

注意

在示例中,我们可以拆分:

- $$$[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]$$$

当然,还有更多可能的答案。