|
|
Use Fenwick tree instead of segment tree It worked. Optimization is really out of this world) I have thought about something like lazy calculations model Can any one help me? I got WA in test #9. But I have no idea where I made a mistake. I need some tests. I might ignored something important. Thanks. me too,got WA in test #9. Have you solve it? You may use segment_tree instead of sqrt_decompose, my solution is segment_tree with very easy idea. Edited by author 27.10.2015 18:43 So, what is the detail of the "segment tree" solution? How to update and query? Thx, in advance.:) A fenwick tree will be faster. Hint : you just need range updates and point queries. My complexity : O(Q * logN * 180). My solution: Cutting the array into blocks, so I can now update a segment with O(sqrt n) each query; therefore, I can get the increase in O(1) while scanning each factor (at most 180 in total). It is obvious that I should prepare all the factors for each number. The complexity of the algorithm is O((sqrt(n) + 180) * m + 180 * n). and .. I reduce a lot of modular and divide operations to get this AC. :P Edited by author 25.10.2015 00:21 |
|
|