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

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] равно максимальному значению в том же диапазоне