← 返回题目列表

AtCoder · tkppc3_h

H. 新生欢迎数字序列 - 困难

中文机器翻译题面 查看原题
配点: 1000 点

問題文

PAKEN,PAKEN的新生,长度是 N 序列 P = {P_1, P_2, P_3, ..., P_N} 从 E869120 收到。 最初 P 的所有元素都是 0 。

PAKEN 你,数字序列 P 按任意顺序执行以下操作,总计 通过执行不超过 550 \ 000 次,我们可以将此序列转换为 我想让它与 A = {A_1, A_2, A_3, ..., A_N} 相同。 选择

  • 操作 1: 1 以上 N 的整数 如果正确答案是满足 x , P_x 的值 更改为 1 。 为
  • 操作 2: 1 以上 N 的整数 如果正确答案是满足 y, z , P_y 的值 添加 P_z 的值。然而, 可能是 y = z 。 另外, P_y 的值为 不得超过 10^{18} 。

PAKEN 由于你还年轻,你不知道该采取什么步骤。为了帮助他,您必须向他展示步骤示例。


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 A_3 ... A_N

出力

应按照以下格式从标准输出执行输出。

Q
(1 回目の操作の情報)
(2 回目の操作の情報)
(3 回目の操作の情報)
...
(Q 回目の操作の情報)

首先,要执行的操作数。 必须输出 Q 。 必须是小于或等于 Q 是 0 以上 550 \ 000 的整数。 下一步 Q 行,每个操作的信息必须输出如下。

(☆) 执行操作 1 时

1 x

这是, 它的意思是执行一个操作来制作 P_x 的 1 。


(★) 执行操作 2 时

2 y z

这是, 它的意思是执行一个操作来制作 P_y 至 意思是执行将 P_z 的值相加的操作。 是小于或等于

制約

  • 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点 ]

    没有其他限制。

入力例1

2
1 4

出力例1

4
1 1
1 2
2 2 2
2 2 2

通过运算,序列的值变为{0, 0} -> {1, 0} -> {1, 1} -> {1, 2} -> {1, 4}。

入力例2

3
1 3 5

出力例2

8
1 1
2 1 1
2 3 1
1 1
2 1 2
2 2 1
2 3 1
1 1

通过运算,序列的值变为{0, 0, 0} -> {1, 0, 0} -> {2, 0, 0} -> {2, 0, 2} -> {1, 0, 2} -> {3, 0, 2} -> {3, 3, 2} -> {3, 3, 5} -> {1, 3, 5}。

作者: E869120 仅由