f033. 攗皥蒽快給我去工作!!!- 續
Tags : BIT 二分搜 分塊 線段樹
Accepted rate : 32人/40人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-02-01 11:49

Content

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

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

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

 
Input

第一行有兩個數字 $\color{black}{n, q}\ $,代表有 $\color{black}{n}\ $ 天工作和 $\color{black}{q}\ $ 筆詢問。

第二行有 $\color{black}{n}\ $ 個數字 $\color{black}{a_1\sim a_n}\ $,代表 $\color{black}{1\sim n}\ $ 天初始的工資。

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

  • $\color{black}{1≤p≤n≤5\times 10^5,1≤q≤10^5}\ $
  • $\color{black}{0≤a_i,c≤1000}\ $
  • $\color{black}{1≤k≤10^9}\ $
Output

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

如果皥蒽就算工作 $\color{black}{n}\ $ 天候還是賺不到足夠的錢,輸出 $\color{black}{meh}\ $

Sample Input #1
5 5
1 2 3 4 5
2 4
2 16
1 5 0
2 11
2 9
Sample Output #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
Hint :

$\color{black}{10\%:n,q≤1000}\ $

$\color{black}{90\%:無特別限制}\ $

Tags:
BIT 二分搜 分塊 線段樹
出處:
第五屆簡單的小競賽 [管理者: becaido (Caido) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
29206 SUNGOD (黑龍炎使.煞氣ㄟSUNGOD) f033
tag可加個 分塊法
295 2022-02-05 17:01
29149 fire5386 (becaidorz) f033
352 2022-02-01 20:15