問題一覧 > 通常問題

No.2809 Sort Query

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 56
作問者 : highlighter / テスター : warabi0906 hirayuu_yc silv723 fact493 Magentor keisuke6 zeta7532
お気に入りにしたユーザー ProblemId : 10865 / 自分の提出
問題文最終更新日: 2025-09-27 11:48:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 436 ('09 Contest 002 day1) (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of length $N$. You are given $Q$ queries; process them in the given order.

Each query is one of the following $3$ types.

  • 1 k x $\colon$ Change the value of $A_{k}$ to $x$.
  • 2 $\colon$ Sort $A$ in ascending order of value.
  • 3 k $\colon$ Output the value of $A_{k}$.

Constraints

  • $1 \leq N,Q \leq 3 \times 10^{5}$
  • $1 \leq A_{1} , A_{2} , \cdots , A_{N} \leq 10^{18}$
  • For queries of the $1$st format,
    • $1 \leq k \leq N$
    • $1 \leq x \leq 10^{18}$
  • For queries of the $3$rd format,
    • $1 \leq k \leq N$
  • All input values are integers.

Input

$N~~~Q$
$A_{1}~~~A_{2} ~~\ldots ~~A_{N}$
$\mathrm{query}_{1}$
$\mathrm{query}_{2}$
$\vdots$
$\mathrm{query}_{Q}$

Here, $\mathrm{query}_{i}$ represents the $i$-th query and is given in one of the following formats.

$1~~~k~~~x$
$2$
$3~~~k$

Output

Let $q$ be the number of queries of the $3$rd format. Output $q$ lines. On the $j(1 \leq j \leq q)$-th line, output the answer to the $j$-th query among the queries of the $3$rd format.

Sample

Sample 1
Input
3 3
2 4 5
1 1 7
2
3 1
Output
4

The final elements of $A$ are $A= \left\lbrace 4,5,7 \right\rbrace$.

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