e-olymp
Задачи

Трое из Простоквашино 3

Трое из Простоквашино 3

prb4493 - Печкин, а я научился работать с деревом отрезков.

- Заняться тебе нечем просто, Шарик. Лучше бы помог мне письма разносить.

- Ну, Печкин, я уже даже выполнил задания Дяди Федора и Кота Матроскина, только этот Матроскин не захотел проверять, правильно ли я сделал.

- Ну ладно, давай я проверю, что там надо было сделать?

- У меня был массив чисел и множество запросов – представляющих собой либо запрос на изменение в массиве, либо содержащий число, для которого мне нужно было найти такой промежуток [l; r], что максимум на этом промежутке был бы равен заданному числу. Можешь прочитать предыдущую задачу.

- Разберемся…

Входные данные

В первой строке содержится одно число N (1N106) – количество элементов в массиве. В следующей строке находится N целых, неотрицательных чисел, не превосходящих 109 – сами элементы массива. Затем следует число M (1M105) – количество запросов. Затем М строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число x, и Шарику надо было найти два числа l и r, такие, что максимум на промежутке [l; r], был равен x. Если же тип запроса равен двум, то далее следует два числа pos и val и это значит, что элемент массива, стоящий на позиции pos, теперь изменен и он стал равен значению val. Далее для каждого запроса с номером один содержится по строке с двумя числами l и r – ответы Шарика.

Выходные данные

Для каждого ответа Шарика выведите "Yes", если он ответил правильно и "No", если Шарик ошибся. Заметьте, что хотя в предыдущей задаче было необходимо найти минимальные числа l и r, здесь Печкин проверять этого не будет.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
5
1 2 4 3 1
5
1 4
1 5
2 3 5
1 1
1 4
1 3
1 5
5 5
2 4
Выходные данные
Yes
No
Yes
No
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года