問題一覧 > 通常問題

No.3298 K-th Slime

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : Nafmo2 / テスター : dyktr_06 くらげ sepa38 おのせ
ProblemId : 12627 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-04 16:40:52

問題文

$N$ 個のスライムが入っている箱があります。各スライムの大きさはそれぞれ $A_1, A_2, \ldots, A_N$ です。

$Q$ 個のクエリが与えられるので、順に処理してください。与えられるクエリは $3$ 種類であり、以下に示すいずれかの形式で与えられます。

  • 1 x : 大きさ $x$ のスライムを新しく生成し、箱の中に入れる。
  • 2 y : 箱の中の $K$ 番目に小さいスライムを $1$ つ取り出す。そのスライムの大きさを $y$ 大きくし、箱の中に戻す。
  • 3 : 箱の中の $K$ 番目に小さいスライムの大きさを出力する。

制約

  • $1 \leq K \leq N \leq 100{,}000$
  • $1 \leq Q \leq 100{,}000$
  • $1 \leq A_i \leq 10^{9} \ (1 \leq i \leq N)$
  • $1 \leq x, y \leq 10^{9}$
  • 入力は全て整数

入力

$N \ K \ Q$
$A_1 \ A_2 \ \ldots \ A_N$
$query_1$
$\vdots$
$query_Q$

$i$ 番目のクエリ $query_i$ は次の $3$ 種類のいずれかの形式で与えられる。

1 x

2 y

3

出力

$3$ 種類目のクエリが $X$ 個あるとき、$X$ 行出力してください。$i$ 行目 $(1 \leq i \leq X)$ には、$i$ 個目の $3$ 種類目のクエリに対する答えを出力してください。

サンプル

サンプル1
入力
5 3 8
1 2 3 4 5
1 6
3
2 4
3
1 10
3
2 10
3
出力
3
4
4
5

最初、箱の中には $[1,\ 2, \ 3, \ 4, \ 5]$ のスライムが入っています。(以降、$n$ 個のスライムが入っている箱の中を $[a_1, \ldots, a_n]$ で表します)

  • クエリ $1$ ： 大きさ $6$ のスライムを生成
    • 箱： $[1,\ 2, \ 3, \ 4, \ 5, \ 6]$
  • クエリ $2$ ： $3$ 番目に小さいスライムの大きさを出力
    • 出力： $3$
  • クエリ $3$ ： $3$ 番目に小さいスライムを取り出し、$4$ 大きくして戻す
    • 箱： $[1,\ 2, \ 4, \ 5, \ 6, \ 7]$
  • クエリ $4$ ： $3$ 番目に小さいスライムの大きさを出力
    • 出力： $4$
  • クエリ $5$ ：大きさ $10$ のスライムを生成
    • 箱： $[1,\ 2, \ 4, \ 5, \ 6, \ 7, \ 10]$
  • クエリ $6$ ： $3$ 番目に小さいスライムの大きさを出力
    • 出力： $4$
  • クエリ $7$ ： $3$ 番目に小さいスライムを取り出し、$10$ 大きくして戻す
    • 箱： $[1,\ 2, \ 5, \ 6, \ 7, \ 10, \ 14]$
  • クエリ $8$ ： $3$ 番目に小さいスライムの大きさを出力
    • 出力： $5$
サンプル2
入力
5 3 13
3 8 5 2 9
2 6
2 1
1 1
1 10
2 7
1 4
3
1 10
1 8
3
1 5
2 3
3
出力
4
4
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。