f033. 攗皥蒽快給我去工作！！！- 續

內容

皥蒽在沒日沒夜的工作後，終於存夠了錢，準備買東西給他的老婆 Dora 和他兩個嗷嗷待哺的小孩。結果走在路上時，竟然有人把他的錢搶走了，還揍了他一頓。

這下他慘了，錢全部不見了，身上又受傷了，於是他回去之前工作的地方，想要繼續工作來賺錢。看到他一回來，所有工作的人便都看著他笑，有的叫道，「攗皥蒽，你臉上又添上新傷疤了！」他不回答，對老闆說，「給我一份工作。」他們又故意的高聲嚷道，「你一定又被別人偷東西了！」攗皥蒽睜大眼睛說，「你怎麼這樣憑空汙人清白……」「什麼清白？我前天親眼見你被偷，還被吊著打。」攗皥蒽便漲紅了臉，額上的青筋條條綻出，爭辯道，「被打不能算被偷……被偷！……攗皥蒽的事，能算被偷麼？」接連便是難懂的話，什麼「咖哩拌飯」，什麼「外賣」之類，引得眾人都哄笑起來：公司內外充滿了快活的空氣。

這時有一個自稱 CK (Chlamydosaurus kingii) 的人來找攗皥蒽，對他說：「我這邊有幾份工作可以給你：總共有 $n$ 天，每天各有一份工作，工資為 $a_{i}$ ，你可以選擇從第 $1$ 天工作到第 $x$ 天，只是在過程中 $a_{i}$ 可能有所變動。」攗皥蒽回答：「所以假設我現在總共想要賺 $k$ 元，我可以找到一個最小的 $x$ ，使第 $1$ 天到第 $x$ 天的工資總和大於等於 $k$ 嗎？」CK：「對啊！」

輸入說明

第一行有兩個數字 $n, q$ ，代表有 $n$ 天工作和 $q$ 筆詢問。

第二行有 $n$ 個數字 $a_{1} \sim a_{n}$ ，代表 $1 \sim n$ 天初始的工資。

接下來有 $q$ 行，每行第一個數字為 $t$ ：如果 $t = 1$ ，接下來會輸入 $p$ 和 $c$ ，代表第 $p$ 天的工資 $a_{p}$ 改為 $c$ ；若 $t = 2$ ，接下來會輸入 $k$ ，代表皥蒽想賺到的錢。

$1 \leq p \leq n \leq 5 \times 10^{5} ， 1 \leq q \leq 10^{5}$
$0 \leq a_{i}, c \leq 1000$
$1 \leq k \leq 10^{9}$

輸出說明

對於每個 $t = 2$ 的情況，輸出一個最小的 $x$ ，代表皥蒽從第一天工作到第 $x$ 天賺到的錢大於等於 $k$ 。

如果皥蒽就算工作 $n$ 天候還是賺不到足夠的錢，輸出 $m e h$

範例輸入 #1

範例輸出 #1

3
meh
meh
4

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 0.5s , <1M
公開測資點#1 (5%): 0.5s , <1M
公開測資點#2 (5%): 0.5s , <10M
公開測資點#3 (5%): 0.5s , <10M
公開測資點#4 (5%): 0.5s , <10M
公開測資點#5 (5%): 0.5s , <10M
公開測資點#6 (5%): 0.5s , <10M
公開測資點#7 (5%): 0.5s , <10M
公開測資點#8 (5%): 0.5s , <10M
公開測資點#9 (5%): 0.5s , <10M
公開測資點#10 (5%): 0.5s , <10M
公開測資點#11 (5%): 0.5s , <10M
公開測資點#12 (5%): 0.5s , <10M
公開測資點#13 (5%): 0.5s , <10M
公開測資點#14 (5%): 0.5s , <1M
公開測資點#15 (5%): 0.5s , <10M
公開測資點#16 (5%): 0.5s , <10M
公開測資點#17 (5%): 0.5s , <10M
公開測資點#18 (5%): 0.5s , <10M
公開測資點#19 (5%): 0.5s , <10M

提示：

$10 % ： n, q \leq 1000$

$90 % ：無特別限制$

標籤:

BIT 二分搜分塊線段樹

出處:

第五屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
29206	SUNGOD (黑龍炎使．煞氣ㄟSUNGOD)	f033	tag可加個分塊法	473	2022-02-05 17:01
29149	fire5386 (becaidorz)	f033	binary search + segment tree	545	2022-02-01 20:15