ソートによる高速化まとめ (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

N 要素の数列 A が与えられます。次の 2 つの操作をおこなうプログラムを作成してください。

・ update(k, x): 列の先頭から k 番目の値を x に変更する。
・ get(k): 数列 A の中から大きい順で k 番目の値を出力する。

入力される値

N Q
A_1 A_2 A_3 ... A_N
query_1 k_1 x_1
query_2 k_2 x_2
...
query_Q k_Q x_Q

・ 1 行目に、数列の要素数 N とクエリの数 Q が与えられます。
・ 2 行目に数列 A が与えられます。
・続く Q 行にクエリが与えられます。 query_i はクエリの種類を示し、 update または get が与えられます。また、 query_i が get であるときは、 x_i にかならず 0 が入ります。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 各 get クエリの結果を改行区切りで出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N ≦ 1,000
・ 1 ≦ Q ≦ 1,000
・ 1 ≦ A_i, x_i ≦ 1,000,000,000
・ 1 ≦ k_i ≦ N
・ get クエリが 1 つ以上与えられる

入力例1: 6 4
6 5 4 3 2 1
get 1 0
update 6 7
get 1 0
get 6 0

出力例1: 6
7
2

問題一覧へ戻る