K - Colorful Balls
問題文
一方の端が開いていて、もう一方の端が閉じている細長い筒があり、開いているほうが左になるように置かれています。
また、様々な色で塗られたボールがあり、各ボールは $1$ 以上 $10^{9}$ 以下の整数で表される色で塗られています。
はじめ、筒の中は空です。クエリが $Q$ 回与えられるので、順番に処理してください。
各クエリは以下の3種類のいずれかです。
1 x c: 色 $c$ のボールを左から $x$ 個追加する2 x: 現在の筒の左から $1, 2, \ldots, x$ 番目のボールを取り除く3 x: 現在の筒の左から $x$ 番目のボールの色を出力する
なお、筒は十分に細く、ボールの順序が入れ替わることはないものとします。
制約
- $1 \leq Q \leq 2 \times 10^{5}$
- クエリ
1に対して、 $1 \leq x \leq 10^{9}$ - $1 \leq c \leq 10^{9}$
- クエリ
2,3において、その時点で筒の中に $x$ 個以上 ($x \geq 1$) のボールが存在する - 入力はすべて整数
部分点
以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられます。
- (10点) $Q \leq 5000$, クエリ
1,2に対しては常に $x = 1$ - (30点) $Q \leq 5000$
- (60点) 追加の制約なし
入力
入力は、以下の形式で標準入力から与えられます。
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$
各クエリ $\mathrm{query}_i$ は、以下に示す $3$ つの形式のいずれかである。
$1$ $x$ $c$
$2$ $x$
$3$ $x$
出力
クエリ3の個数を $q$ 個として、$q$ 行出力せよ。
$j (1 \leq j \leq q)$ 行目には、クエリ3のうち $j$ 個目のものに対する答えを出力せよ。
6
1 1 10000
1 1 14142
3 2
1 1 17320
2 1
3 1
10000
14142
筒の中の状態を左から順番に、数列で表すことにします。
始め、筒の中は $()$ です。
1番目のクエリは1 1 10000です。筒の中の状態は$(10000)$ になります。
2番目のクエリは1 1 14142です。筒の中の状態は$(14142, 10000)$ になります。
3番目のクエリは3 2です。左から $2$ 番目の色である $10000$ を出力します。
4番目のクエリは1 1 17320です。筒の中の状態は$(17320, 14142, 10000)$ になります。
5番目のクエリは2 1です。筒の中の状態は$(14142, 10000)$ になります。
6番目のクエリは3 1です。左から $1$ 番目の色である $14142$ を出力します。
この入力は部分点1の制約を満たします。
6
1 3 1
1 4 2
1 5 3
3 7
2 7
3 3
2
1
1番目のクエリは1 3 1です。筒の中の状態は$(1, 1, 1)$ になります。
2番目のクエリは1 4 2です。筒の中の状態は$(2, 2, 2, 2, 1, 1, 1)$ になります。
3番目のクエリは1 5 3です。筒の中の状態は$(3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1)$ になります。
4番目のクエリは3 7です。左から $7$ 番目の色である $2$ を出力します。
5番目のクエリは2 7です。筒の中の状態は$(2, 2, 1, 1, 1)$ になります。
6番目のクエリは3 3です。左から $3$ 番目の色である $1$ を出力します。
この入力は部分点2の制約を満たします。
6
1 1000000000 1
1 1000000000 2
1 1000000000 3
3 2500000000
2 2999999999
3 1
1
1
クエリ2,3において、 $x$ が32bit整数型に収まらないことがあります。
この入力は部分点2の制約を満たします。