Noi模拟 市场 线段树

考场上想到了以前写的这道题 :http://oi.self-jqe.win/?p=787

觉得开根号,除法之类的越整,序列越相似,那种不能批处理就暴力,能批量处理就批量处理的算法复杂度都有保证,看数据范围10^5发现貌似比正常的10^6的小一些,觉得很有可能就是这种做法,然后就写了。

具体就是

1 我们考虑一个序列,整除几次整个序列会趋向于相同。

2 11 / 4 = 2 减少了9 12 / 4 = 3也减少了9 我们发现相邻的数字也有用区间减统一处理的趋势,而且打了个表发现,好像只要两头一样,中间也肯定一样。

然后我们就可以暴力了,维护min,max,sum,lzy

区间加正常来。

除如果发现这段的max – max/ val == min – min / val 那么就是这段可以统一处理,就算下少了多少,当区间加处理,否则就继续递归。

发表评论