Discussion @ 2062. Ambitious Experiment @ Timus Online Judge

use SQRT decompose.

Posted by Adhambek 27 Oct 2015 13:53

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.

Posted by Alexandru Valeanu 15 Nov 2015 06:01

A fenwick tree will be faster.
Hint : you just need range updates and point queries.
My complexity : O(Q * logN * 180).

Discussion of Problem 2062. Ambitious Experiment