No.2809 Sort Query
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 :
highlighter
/ テスター :
warabi0906
hirayuu_yc
silv723
fact493
Magentor
keisuke6
zeta7532
タグ : / 解いたユーザー数 52
作問者 :
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![keisuke6](https://pbs.twimg.com/profile_images/1675785204974354432/k3Bvkvyj.jpg)
問題文最終更新日: 2024-07-12 20:55:23
問題文
長さ $N$ の数列 $A$ が与えられます。クエリが $Q$ 個与えられるので、与えられた順番に処理してください。
クエリは次の $3$ 種類のいずれかです。
1 k x
$\colon$ $A_{k}$ の値を $x$ に変更する。
2
$\colon$ $A$ を値の昇順に並び替える。
3 k
$\colon$ $A_{k}$ の値を出力する。
制約
-
$1$ 番目の形式のクエリについて、
- $1 \leq k \leq N$
- $1 \leq x \leq 10^{18}$
-
$3$ 番目の形式のクエリについて、
- $1 \leq k \leq N$
- 入力はすべて整数
入力
$N~~~Q$ $A_{1}~~~A_{2} ~~\ldots ~~A_{N}$ $\mathrm{query}_{1}$ $\mathrm{query}_{2}$ $\vdots$ $\mathrm{query}_{Q}$
ただし、 $\mathrm{query}_{i}$ は $i$ 個目のクエリを表しており、次の形式のいずれかで与えられる。
$1~~~k~~~x$
$2$
$3~~~k$
出力
$3$ 番目の形式のクエリの個数を $q$ として $q$ 行出力せよ。 $j(1 \leq j \leq q)$ 行目には $3$ 番目の形式のクエリのうち $j$ 個目のものに対する答えを出力せよ。
サンプル
サンプル1
入力
3 3 2 4 5 1 1 7 2 3 1
出力
4
最終的な $A$ の要素は、 $A= \left\lbrace 4,5,7 \right\rbrace$ となっています。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。