Is this problem solvable in any other way not using Segment Tree?
Can this problem solved using Fenwick Tree?

gcd ~ min
but, we can't use fenwick tree, because, when update, new minimum should be no more than previous.

but I could be wrong :)

I used gcd tree and set. And I got TL 17. Then I remade my recursive update function to nonrecursive. I got AC. Then I remade my recursive get_gcd function to nonrecursive function. AND GOT TL AGAIN!

Using a treap is another nice way.
AC 0.296 without any optimizations (and 0.234 after some :) )

Edited by author 20.09.2011 21:38

I use SQRT-decomposition. Accept 0.468 on Java.

I also solved it by Sqrt-decomposition. Accept 0.292 on C++

I used balanced bst (AVL tree), keeping GCD for each subtree. Got 0.39
Thought about segment tree but found it not so elegant. How does your segment tree solution look?

ibra, Pavel Kovalenko, thanks for sqrt-decomposition hint!

Edited by author 01.10.2011 21:08

Did you use some modifications to Sqrt-decomposition? I seem to be unable to AC it. I use C++ (on Java it's a bit tougher) and I use multiset for storing integer, not a vector. I get TLE 22 ... I tried to modify sizes, but that doesn't seem to help.Did you use Sqrt-decomp twice?

Could you explain a little more about "SQRT-decomposition" or where I can find an introduction to it?
I tried google it but it's nowhere.
Thanks!

Could you explain a little more about "SQRT-decomposition" or where I can find an introduction to it?
I tried google it but it's nowhere.
Thanks!

I got TL with treap ><, it's strange.
Can someone help me?
Code here: http://www.everfall.com/paste/id.php?bkqpp0lvnsye

Edited by author 18.07.2012 17:56

Edited by author 18.07.2012 17:56