Каков наиболее оптимальный способ решения этой проблемы?

Question

Я видел этот вопрос по кодированию на онлайн-конкурсе по кодированию, но не смог найти наиболее оптимального решения.Вот вопрос:
"Вам дан массив A из N целых чисел и Q запросов. Каждый запрос имеет следующий тип:
1 pos val: Обновите элемент с индексом pos до val
2 pos: Найти наименьший индекс i, меньший или равный pos, так что все элементы между i и pos одинаковы.Сегмент дерева будет представлять.

Answer 1

Вот подход O (N + Q log ^ 2 N):

1. Построить дерево сегментов для данного массива
2. В каждом узле дерева сегментов хранить минимальное количество интервалови максимальное число в интервале
3. Теперь запросы типа 1 могут быть выполнены простым обновлением в сегментном дереве
4. Для запросов типа 2 мы можем использовать бинарный поиск, чтобы найти наименьшее i такое, что минимальное значение вдиапазон [i, pos] равен максимальному значению в том же диапазоне