← 返回题目列表

AtCoder · maximum_cup_2018_e

E. 中断数组

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

配点 : 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。