← 返回题目列表

AtCoder · typical90_bp

068. 配对信息(★5)

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

配点: 5 点

問題文

长度 小于或等于 N 整数序列 给出 A = (A_1, A_2, \ldots, A_N) 。 最初,您对这个整数序列一无所知。 有关

整数列 A (统称为该事件)的信息和问题 给出了 Q 。从一开始 i 番目 (1 \leq i \leq Q) 事件是 4 整数集 查找 (T_i, X_i, Y_i, V_i) ,是这样的: 当

  • T_i = 0 时,这是 这意味着给出了信息 A_{X_i} + A_{Y_i} = V_i 。在这里,请务必 假设 X_i+1=Y_i 。
  • T_i = 1 时,这是 这意味着给出了信息 A_{X_i} = V_i 当假设 A_{Y_i} 的值是多少?意味着问题。
    • 更准确地说, 使所有 A_{X_i}=V_i 和 按字典顺序比较 A_{X_j} + A_{Y_j} = V_j \ (1 \leq j \lt i, T_j = 0) 都成立的长度。 在 N 整数序列 给出 A 中, 输出 A_{Y_i} 的值是多少?代表问题。

逐步浏览事件并回答每个事件的问题。 不过,提问时的答案 当 A_{Y_i} 无法以一种方式确定时,改为 Ambiguous 。

制約

  • 1\leq N\leq10^5
  • 1\leq Q\leq10^5
  • T_i=0 或 至少 T_i=1\ (1\leq i\leq Q)
  • 1\leq X_i,Y_i\leq N\ (1\leq i\leq Q)
  • T_i=0 如果 X_i+1=Y_i\ (1\leq i\leq Q)
  • 0\leq V_i\leq 2\times10^9\ (1\leq i\leq Q)
  • 没有给出矛盾的输入。
    • 换句话说,i=1,2,\ldots,Q , T_i=0 如果 T_j=0\ (1\leq j\leq i) 小于 j 以同样的方式定义 A_{X_j}+A_{Y_j}=V_j 都成立, 使所有 T_i=1 如果 A_{X_i}=V_i 和 按字典顺序比较 T_j=0\ (1\leq j \lt i) 小于 j 以同样的方式定义 A_{X_j}+A_{Y_j}=V_j 都成立的长度。 N 整数序列 给出 A 存在。
  • 所有输入均为整数

入力

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

N
Q
T_1 X_1 Y_1 V_1
T_2 X_2 Y_2 V_2
\vdots
T_Q X_Q Y_Q V_Q

出力

请按顺序输出每个问题的答案。 但是,如果在提问时答案不确定,则 Ambiguous 。


入力例 1

4
7
0 1 2 3
1 1 2 1
1 3 4 5
0 3 4 6
1 3 4 5
0 2 3 6
1 3 1 5

出力例 1

2
Ambiguous
1
2

对于每个问题,答案是:

  • 1 第二个问题(i=2), 满足A_1=1 和 A_1+A_2=3 的序列 A 就是全部 它是 A_2=2 满足,所以应该输出的是 2 。
  • 2 第二个问题(i=3), 满足A_3=5 和 A_1+A_2=3 的序列 A 有 直到 (A_1,A_2,A_3,A_4)=(1,2,5,10) 呀 请注意,它可能是 (A_1,A_2,A_3,A_4)=(3,0,5,0) 等 由于 A_4 没有单一值,因此应该输出的是 有一块木板,分为 Ambiguous 。
  • 3 第二个问题(i=5), 满足A_3=5 和 A_1+A_2=3,A_3+A_4=6 的序列 A 就是全部 它是 A_4=1 满足,所以应该输出的是 1 。
  • 4 第二个问题(i=7), 满足A_3=5 和 A_1+A_2=3,A_3+A_4=6,A_2+A_3=6 的序列 A 就是全部 它是 A_1=2 满足,所以应该输出的是 2 。

入力例 2

15
25
0 11 12 41
0 1 2 159
0 14 15 121
0 4 5 245
0 12 13 157
0 9 10 176
0 6 7 170
0 2 3 123
0 7 8 167
0 3 4 159
1 12 11 33
0 10 11 116
0 8 9 161
1 9 12 68
1 12 12 33
1 7 12 74
0 5 6 290
1 8 9 93
0 13 14 127
1 10 12 108
1 14 1 3
1 13 8 124
1 12 11 33
1 12 10 33
1 5 15 194

出力例 2

8
33
33
33
68
33
144
93
8
108
118