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


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

學校 : 國立交通大學
編號 : 95834
來源 : [140.113.213.76]
最後登入時間 ：
2023-09-25 22:02:42
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)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
f033. 攗皥蒽快給我去工作！！！- 續 -- 第五屆簡單的小競賽 | From: [114.25.104.225] | 發表日期 : 2022-02-05 19:14

sqrt decomposition

 
ZeroJudge Forum