配点 : 100 点
問題文
数列S = { 1 } 通过。下面2类型的求和查询 请运行q次。 任何满足
A,i,j : S[k] = i 的 对于k,“ 删除S[k]并将其替换为数字序列。 插入V = { i,j,i } 。
B,i,j : 对于先前查询的所有可能序列,S[a] = i, S[b] = j很满意, 当|a-b|为最小值时 对于a, b,{ 找出 S[k] | (min(a, b) < k < max(a, b)) }中包含的数字类型,然后输出其中最小的数字。
制約
3 \leq q \leq 200000
i,j是一个非负整数。
1 \leq i,j \leq q
查询 A 始终传递给前两个。
查询A, 当我输入i仅存在于序列中的数字,j是序列中不存在的最小正整数。
查询B, 当我输入i,j仅出现在序列中存在的数字中, 代表第i \neq j。
入力
输入是按以下格式从标准输入给出的。
q c_1 i_1 j_1 : c_q i_q j_q
c_k 是 您也可以写 A 或 至少 B 和k 个查询类型 每当 (1\leq k\leq q)。
出力
查询B完成时, 查询1行 请输出B的结果。
入力例 1
7 A 1 2 A 1 3 A 2 4 A 2 5 B 3 5 A 1 6 B 3 6
出力例 1
2 1
{ 1 }
这是初始状态。从现在开始,我们将列出可能的数字序列。
- A,1,2
{ 1,2,1 }
- A,1,3
{ 1,3,1,2,1 } , { 1,2,1,3,1 }
- A,2,4
{ 1,3,1,2,4,2,1 } , { 1,2,4,2,1,3,1 }
- A,2,5
{ 1,3,1,2,5,2,4,2,1 } , { 1,3,1,2,4,2,5,2,1 } , { 1,2,5,2,4,2,1,3,1 } , { 1,2,4,2,5,2,1,3,1 }
- B,3,5
对于每个序列,最接近的 查找3和 按字典顺序比较5之间的数字类型。
每个序列中的值是2,3,3,2所以2。
- A,1,6
{ 1,6,1,3,1,2,5,2,4,2,1 } , { 1,6,1,3,1,2,4,2,5,2,1 } , { 1,6,1,2,5,2,4,2,1,3,1 } , { 1,6,1,2,4,2,5,2,1,3,1 } , { 1,3,1,6,1,2,5,2,4,2,1 } , { 1,3,1,6,1,2,4,2,5,2,1 } , { 1,2,5,2,4,2,1,6,1,3,1 } , { 1,2,4,2,5,2,1,6,1,3,1 } , { 1,3,1,2,5,2,4,2,1,6,1 } , { 1,3,1,2,4,2,5,2,1,6,1 } , { 1,2,5,2,4,2,1,3,1,6,1 } , { 1,2,4,2,5,2,1,3,1,6,1 }
- B,3,6
每个序列中的值是1,1,4,4,1,1,4,4,1,1,4,1所以, 您最多只能移动到1。