Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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を出力します。