Трое из Простоквашино 3
- Печкин, а я научился работать с деревом отрезков.
- Заняться тебе нечем просто, Шарик. Лучше бы помог мне письма разносить.
- Ну, Печкин, я уже даже выполнил задания Дяди Федора и Кота Матроскина, только этот Матроскин не захотел проверять, правильно ли я сделал.
- Ну ладно, давай я проверю, что там надо было сделать?
- У меня был массив чисел и множество запросов – представляющих собой либо запрос на изменение в массиве, либо содержащий число, для которого мне нужно было найти такой промежуток [l; r], что максимум на этом промежутке был бы равен заданному числу. Можешь прочитать предыдущую задачу.
- Разберемся…
Входные данные
В первой строке содержится одно число N (1 ≤ N ≤ 10^6) – количество элементов в массиве. В следующей строке находится N целых, неотрицательных чисел, не превосходящих 10^9 – сами элементы массива. Затем следует число M (1 ≤ M ≤ 10^5) – количество запросов. Затем М строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число x, и Шарику надо было найти два числа l и r, такие, что максимум на промежутке [l; r], был равен x. Если же тип запроса равен двум, то далее следует два числа pos и val и это значит, что элемент массива, стоящий на позиции pos, теперь изменен и он стал равен значению val. Далее для каждого запроса с номером один содержится по строке с двумя числами l и r – ответы Шарика.
Выходные данные
Для каждого ответа Шарика выведите "Yes", если он ответил правильно и "No", если Шарик ошибся. Заметьте, что хотя в предыдущей задаче было необходимо найти минимальные числа l и r, здесь Печкин проверять этого не будет.