The dynamic RMQ problem goes as follows:

Given an array of integers $$$a$$$ of length $$$n$$$ and $$$q$$$ queries of $$$2$$$ types:

1. $$$l\ r$$$ — find the minimum on $$$a[l..r]$$$
2. $$$i\ x$$$ — make $$$a_i = x$$$

If the number of updates $$$\gt \gt$$$ the number of queries (which may occur in MO algorithm for example, where we can have $$$O(n)$$$ min queries and $$$O(n\sqrt n) $$$ updates), what is the most efficient way to solve the problem?

We obviously need smth faster than $$$O(\log(n) )$$$ per update (which is achievable with a ton of ways), like $$$O(1)$$$ or maybe $$$O(\log{\log{n} }) $$$.

I though about it for a while but wasn't able to come up even with sublinear solution for querying min while preserving $$$O(1)$$$ update time.

Current rating graph looks like this:

But it should look like this:

MikeMirzayanov, when rating graph will be improved?

How to solve today's C problem if alphabet is not $$$26$$$ characters but rather $$$O(n)$$$? I could only come up with simple offline $$$O(q \sqrt n)$$$ solution using basic MO algorithm. Any ideas?