Re: use SQRT decompose.

Posted by

Sunnat 27 Oct 2015 18:42

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*

Re: use SQRT decompose.

Posted by

lyonlys 28 Oct 2015 01:07

So, what is the detail of the "segment tree" solution? How to update and query?

Thx, in advance.:)

Re: use SQRT decompose.

A fenwick tree will be faster.

Hint : you just need range updates and point queries.

My complexity : O(Q * logN * 180).