P3396 哈希冲突

一开始看着题目毫无思路...
只有一个暴力才能维持的了10分的样子...
想着打开时的标签:分块....
死活不会统计...
然后弃疗...
换了一个方向思考,,,
首先如果查询x > y肯定都不用管..直接输出0
考虑模数在n范围以内,那么对于模数特别大的情况,发现每个池子的数很少,可以暴力统计。
对于模数小的情况,发现他的预处理很简单的样子...
然后就发现,,,把大于sqrt(n)的数暴力处理是在O(\sqrt n)的,把小于$\sqrt n$的数更新也是O(\sqrt n)
发现这样处理时间O(n \sqrt n)

c++代码如下:

 

2018年4月17日 0 / /
Tag:  No Tags

1 + 9 =