養樹場
發布時間: Sept. 8, 2024, 8:34 p.m. 最後更新時間: Sept. 9, 2024, 7:59 p.m. 時間限制: 1000ms 記憶體限制: 128M
hush為了維持生計開了一間養樹場，在他的細心栽培之下，裡面的樹長的玉樹臨風、樹大招風。為了確保樹木們的品質，hush會不定期抽檢養樹場，但是樹木們實在是太多了，所以他決定應用統計學的抽樣法，只去看第k大的樹有多大。
有的時候像是學測或是開學前，hush會接到屠宰場的訂單，跟他要木頭；又有時候他看到木價上漲他就會移植樹木到養樹場種。
但是hush實在是太忙了，他會告訴你養樹場的狀況，但需要請你幫他算出抽檢的樣品大小有多大。
第一行有兩個整數$n,q$，代表有$n$顆樹$q$個操作
接下來有$n$個正整數$a_1, a_2, ..., a_n$，代表樹的大小
最後會有$q$行，每行第一個數代表操作的種類：
$1$ $k$代表抽樣，$k$整數，代表詢問第$k$大的樹的大小
$2$ $w$代表接單，$w$整數，代表砍掉一棵大小為$w$的樹
$3$ $w$代表移植，$w$整數，代表移植一棵大小為$w$的樹
($1\le n\le 10^5$)
($\forall i,1\le i\le n, 1\le a_i\le 10^5$)
($0\le q\le 10^4$)
($1\le w\le 10^5$)
(保證砍掉的樹必定存在養樹場內，且詢問第$k$大的$k$不超過養樹場現有的樹木量)
對於每個詢問$1 k$，輸出一行答案代表(非嚴格)第$k$大的樹的大小
複製範例
6 6 1 3 4 3 6 2 1 4 1 1 2 4 1 2 3 7 1 6
3 6 3 1
