AT_past202203_m ランキング

[problemUrl]: https://atcoder.jp/contests/past202203-open/tasks/past202203_m 選手 $ 1 $ 、選手 $ 2 $ 、$ \ldots $ 、選手 $ N $ の $ N $ 人の選手がゲームをしており、 選手 $ i $ の得点は最初 $ P_i $ 点です。 クエリが $ Q $ 個与えられるので、与えられた順番に処理してください。 クエリは次の $ 3 $ 種類のいずれかです。 - `1 a x` : 選手 $ a $ の得点を $ x $ に変更する。 - `2 a` : 現在の選手 $ a $ の得点が、$ N $ 人のうち大きい方から何番目か出力する。具体的には $ r $ 番目であるとき整数 $ r $ を出力する。 - `3 r` : $ N $ 人のうち現在の得点が大きい方から $ r $ 番目の選手を出力する。具体的には選手 $ a $ が $ r $ 番目であるとき整数 $ a $ を出力する。 ただし、最初に与えられる各選手の得点および、 $ 1 $ つめの種類のクエリで与えられる変更後の選手の得点はすべて相異なることが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ query_1 $ $ query_2 $ $ \vdots $ $ query_Q $ $ 3 $ 行目から $ Q+2 $ 行目の各 $ query_i $ は次のいずれかの形で与えられる。 > $ 1 $ $ a $ $ x $ > $ 2 $ $ a $ > $ 3 $ $ r $

$ 2 $ つめおよび $ 3 $ つめの種類のクエリに対する出力を、 与えられた順に改行区切りで出力せよ。

### 制約 - $ 1\ \leq\ N,Q\ \leq\ 5\times\ 10^5 $ - $ 0\leq\ P_i\ \leq\ 10^9 $ - $ P_i\ \neq\ P_j $ $ (i\neq\ j) $ - $ 1\leq\ a\ \leq\ N $ - $ 0\leq\ x\ \leq\ 10^9 $ - $ 1\leq\ r\ \leq\ N $ - $ 1 $ つめの種類のクエリの $ x $ はすべて互いに相異なり、また $ P_i $ のいずれとも相異なる。 - $ 2 $ つめまたは $ 3 $ つめの種類のクエリが $ 1 $ つ以上存在する。 - 入力は全て整数である。 ### Sample Explanation 1 最初、選手 $ 1 $ 、選手 $ 2 $ 、選手 $ 3 $ の得点はそれぞれ $ 10 $ , $ 30 $ , $ 20 $ です。 - $ 1 $ つめのクエリについて、選手 $ 1 $ の得点は $ 3 $ 番目に大きいので $ 3 $ を出力します。 - $ 2 $ つめのクエリについて、$ 1 $ 番目に得点が大きい選手は選手 $ 2 $ であるので $ 2 $ を出力します。 - $ 3 $ つめのクエリによって、選手 $ 2 $ の得点は $ 0 $ に変更されます。 これによって選手 $ 1 $ 、選手 $ 2 $ 、選手 $ 3 $ の得点はそれぞれ $ 10 $ , $ 0 $ , $ 20 $ になります。 - $ 4 $ つめのクエリについて、選手 $ 1 $ の得点は $ 2 $ 番目に大きいので $ 2 $ を出力します。 - $ 5 $ つめのクエリについて、$ 2 $ 番目に得点が大きい選手は選手 $ 1 $ であるので $ 1 $ を出力します。