問題一覧 > 通常問題

No.2809 Sort Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : highlighter / テスター : warabi0906 hirayuu_yc silv723 fact493 Magentor keisuke6 zeta7532
2 ProblemId : 10865 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:55:23

問題文

長さ NN の数列 AA が与えられます。クエリが QQ 個与えられるので、与えられた順番に処理してください。

クエリは次の 33 種類のいずれかです。

  • 1 k x  ⁣:\colon AkA_{k} の値を xx に変更する。
  • 2  ⁣:\colon AA を値の昇順に並び替える。
  • 3 k  ⁣:\colon AkA_{k} の値を出力する。

    • 制約

  • 1≤N,Q≤3×1051 \leq N,Q \leq 3 \times 10^{5}
  • 1≤A1,A2,⋯ ,AN≤10181 \leq A_{1} , A_{2} , \cdots , A_{N} \leq 10^{18}
    • 11 番目の形式のクエリについて、
      • 1≤k≤N1 \leq k \leq N
      • 1≤x≤10181 \leq x \leq 10^{18}
    • 33 番目の形式のクエリについて、
      • 1≤k≤N1 \leq k \leq N
    • 入力はすべて整数

    入力

    N   QN~~~Q
A1   A2  …  ANA_{1}~~~A_{2} ~~\ldots ~~A_{N}
query1\mathrm{query}_{1}
query2\mathrm{query}_{2}
⋮\vdots
queryQ\mathrm{query}_{Q}

    ただし、 queryi\mathrm{query}_{i} は ii 個目のクエリを表しており、次の形式のいずれかで与えられる。 

    1   k   x1~~~k~~~x

    22

    3   k3~~~k

    出力

    33 番目の形式のクエリの個数を qq として qq 行出力せよ。 j(1≤j≤q)j(1 \leq j \leq q) 行目には 33 番目の形式のクエリのうち jj 個目のものに対する答えを出力せよ。

    サンプル

    サンプル1
    入力
    3 3
2 4 5
1 1 7
2
3 1
    出力
    4

    最終的な AA の要素は、 A={4,5,7}A= \left\lbrace 4,5,7 \right\rbrace となっています。

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