He didn't mention that he did binary search over the divisors so I guess he did it over all numbers. Btw, you don't need binary search, you needed to calculate all the divisors so simply see if it fits over all divisors, the complexity is the same.

I just got AC with a normal segtree and an implicit segtree.

What I did was maintain an implicit segtree over the range [1, N * K], and a normal segtree over the given array, i.e. [1, N].

The invariant of the implicit segtree is that for every node, if it exists, it will store the correct minimum value of the range it represents. It will also store a lazy value, which if non zero, means that there was an update at some time on the range it represents, with the value of lazy.

Now when you are updating on the implicit segtree, say the current node completely overlaps with the update interval, then I will mark the lazy value on this node as the current query's value, and free all the nodes in the subtree of this node, since they are not needed anymore.

When I am querying, if I reach a node that completely overlaps with the query interval, and the node is allocated, I will just return the minimum value at this node (which is correct because of the invariant of the implicit segtree).

If I reach a node that completely overlaps with the query interval, but hasn't been allocated, I will first see the lazy value of the closest allocated ancestor of the current node which has a non zero lazy value. If their exist an ancestor with a non zero lazy value, I will return that lazy value. If there doesn't exist any such ancestor, I will query over the segtree made over the original array, as this range hasn't been updated in any way.

It's kind of hard to explain in words, you can try to read the code and see if it helps: Code

Let's write down all values of l and r for all queries, sort them and remove duplicates. One can see that a range between two consecutive elements can be treated as a point (because no query splits it) and there're clearly O(q) such points.

We can build a standard segment tree over this compressed array of query boundaries. Each position should contain a value equal to the smallest element in the given range in the initial array (we can find it using the same segment tree build over the input array. We need to handle "long" ranges carefully: if r - l > n, we can just return the minimum of the entire array). After that, each query is a range assignment/range max in this segment tree.

You're welcome :)

sum of a_i = n Moreover, each a_i can be represented as gcd multiplied by some x_i according to gcd's property. -> sum of gcd * x_i = n ;)

No. I hacked many solutions (yours fails this aswell) with long long overflow) Check something like n = 1, k = 3 500 000 000