Задача А. RMQ

Разделим массив $$$A[0..n-1]$$$ на $$$\sqrt{N}$$$ блоков. Будем поддерживать массив $$$Block[0..\sqrt{N}]$$$, где $$$i$$$-й элемент будет минимальным значениям $$$i$$$-го блока. Каждому блоку изначально установим значение $$$+\infty$$$. При считывании исходного массива $$$A$$$ в каждом блоке будем поддерживать минимальное значение: [ Block[i] = \underset{j \in [i * \sqrt{N}; (i+1) * \sqrt{N})}{\min{A[j]}} ]

Будем отвечать на запрос поиска минимума на полуинтервале $$$[l; r)$$$ за $$$O(\sqrt{N})$$$, проходясь по блокам, полностью входящим в запрос, а также наивно проходясь по элементам блоков, частично входящих в запрос.

На запрос присвоения нового значения в ячейке массива будем отвечать также за $$$O(\sqrt{N})$$$ путём присвоения нового значения в массиве и пересчёта значения блока.

Если запросов всего $$$Q$$$, то итоговая асимптотика решения составляет $$$O(Q * \sqrt{N})$$$.