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).