AT_tkppc3_h.新入生歓迎数列 - Hard

配点：$1000$ 分

パ研的新生 PAKEN 君从 E869120 那里得到了一个长度为 $N$ 的数列 $P = \{P_1, P_2, P_3, \ldots, P_N\}$。最开始，$P$ 的所有元素均为 $0$。

PAKEN 君打算通过对数列 $P$ 进行如下操作，操作顺序任意，总共不超过 $550\,000$ 次，将该数列变为 $A = \{A_1, A_2, A_3, \ldots, A_N\}$。

• 操作 1：选择一个 $1$ 到 $N$ 之间的整数 $x$，将 $P_x$ 的值变为 $1$。
• 操作 2：选择 $1$ 到 $N$ 之间的整数 $y, z$，将 $P_z$ 的值加到 $P_y$ 上。此时 $y$ 可以等于 $z$。此外，$P_y$ 的值不能超过 $10^{18}$。

PAKEN 君还很年幼，不知道该如何操作。为了帮助他，你需要给出一种操作方案的示例。

输入从标准输入读入，格式如下：

$N$ $A_1$ $A_2$ $A_3$ ... $A_N$

输出到标准输出，格式如下：

$Q$
（第 $1$ 次操作的信息）
（第 $2$ 次操作的信息）
...
（第 $Q$ 次操作的信息）

首先输出操作次数 $Q$。**$Q$ 必须是 $0$ 到 $550\,000$ 之间的整数。**接下来的 $Q$ 行，每行描述一次操作，格式如下：

（☆）执行操作 1 时：

$1$ $x$

表示将 $P_x$ 设为 $1$。

（★）执行操作 2 时：

$2$ $y$ $z$

表示将 $P_z$ 的值加到 $P_y$ 上。

限制条件

• $N$ 是 $2$ 到 $200\,000$ 之间的整数。
• $A_1 = 1$。
• $A_i$（$1 \leq i \leq N$）是 $1$ 到 $2^{30} - 1$ 之间的整数。

子任务

子任务 1 [$60$ 分]

• 满足 $N = 2$。

子任务 2 [$140$ 分]

• 满足 $N \leq 8\,000$。

子任务 3 [$80$ 分]

• 满足 $N \leq 16\,000$。

子任务 4 [$230$ 分]

• 满足 $N \leq 25\,000$。

子任务 5 [$270$ 分]

• 满足 $N \leq 160\,000$。

子任务 6 [$220$ 分]

• 无额外限制。

由 ChatGPT 4.1 翻译