作者GYLin (Lynx)
看板Prob_Solve
标题Re: [问题] ZeroJudge-c216
时间Tue Apr 2 20:45:33 2019
大致策略:
1. 把途中所有累积加值都模100000, 原因很明显
2. 当需要计算Sum[L,R]时, 其值为"不考虑爆掉的原本加总"扣掉100000*(区间内爆掉人数)
爆掉人数为: 区间内的Ai个数, 其值加上目前累积加值会超过100000的人们
要计算爆掉人数, 只要维护一个 Map[i][j] 就可以,
Map[i][j] 就是 阵列 1~i, 加上高度 j 会爆掉的人数,
若开普通阵列可能需要 100000*100000 的大小,
但实际上出现的询问只会有 10^6 种,
所以先把询问全部存起来後, 再针对会出现的询问求出爆掉人数,
再回去把存起来的询问解决即可.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.226.107.14
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1554209135.A.08E.html