作者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/cn.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