作者fatcat8127 (胖胖貓)
看板Prob_Solve
標題[問題] 離線處理
時間Tue Apr 9 00:41:55 2019
想問一下關於 ZJ-c710 這題的離線處理，題目是標準RMQ類型
一般莫隊算法是處理離線問題的代表，ZJ-b417的區間眾數是經典
但是這題要取餘數該怎麼下手呢？應該不可能將各個數字計算個數...
雖然題目的標籤處提示是期望空間複雜度為 O(N+M)。
N 應該原始數據，M 代表所有的查詢需要儲存達到符合離線的作法，
但具體的方式就完全卡住。
解法：
( 離線處理=>莫隊 ) 89%(11% TLE，卡在當除數很小但是暴力法查詢倍數導致的TLE)
根據theshold決定採用莫隊還是前綴和計算
訂一個 threshold 來決定當除數小於時透過『前綴和』計算區間內可以被該除數整除
的個數，因為前綴和的計算方式整體記憶體空間不能過大(√ＮxＮ太大，所以才把
threshold調降為50)，若大於等於則採用莫隊算法處理，
這時即便是暴力查詢倍數時間成本也是Ｋ√Ｎ，Ｋ＝√Ｎ/threshold。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1554741717.A.5D2.html
2F：→ oToToT: 這底下的討論之類的可能可以回答你 04/09 10:32
3F：→ fatcat8127: 感謝oT大大 04/09 13:12
4F：→ fatcat8127: 實作了莫隊算法，不過只能拿到89%和一個TLE，原因應 04/12 01:47
5F：→ fatcat8127: 該是累加除數的倍數時太耗時間 04/12 01:47
6F：→ fatcat8127: 感謝 cutecpu 的指導 問題以解決 04/21 07:26
※ 編輯: fatcat8127 (61.231.101.233), 04/21/2019 07:32:16