No.2809 Sort Query
レベル :
/ AI推定難易度 : 1600
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 :
highlighter
/ テスター :
warabi0906
hirayuu_yc
silv723
fact493
Magentor
keisuke6
zeta7532
タグ : / 解いたユーザー数 56
作問者 :
highlighter
/ テスター :
fact493
Magentor
keisuke6
問題文最終更新日: 2025-09-27 11:48:42
English (AI translation)
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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。