發表新討論
#29206: tag可加個 分塊法


SUNGOD (黑龍炎使．煞氣ㄟSUNGOD)

f033. 攗皥蒽快給我去工作！！！- 續 -- 第五屆簡單的小競賽 | From: [123.240.145.218] | 發表日期: 2022-02-05 17:01

把整個區間分成sqrt(n)塊，每塊處理sqrt(n)個元素->紀錄這n塊的資料&總和，修改改那塊就好(O(sqrt(n)))，查詢就每塊總和加起來，加到過頭就直接進那塊裡面找第幾個(O(sqrt(n)))

total:O(n*sqrt(n)) (AC 0.1s)

 

#29208: Re:tag可加個 分塊法


fire5386 (becaidorz)

f033. 攗皥蒽快給我去工作！！！- 續 -- 第五屆簡單的小競賽 | From: [114.25.104.225] | 發表日期: 2022-02-05 19:14

sqrt decomposition

ZeroJudge Forum