Трое из Простоквашино 2
- Матроскин, а я дерево отрезков научился строить.
- Шарик, лучше бы ты будку новую построил, чем всякую ерунду.
- Ну Матроскин, ну я уже и Дяде Федору код показывал, можешь посмотреть в предыдущей задаче, а тебе новую функцию покажу – изменение.
int update(int v, int left, int right, int pos, int val) {
if (left == right) {
t[v] = val;
return 0;
}
int mid = (left+right) / 2;
if (pos <= mid)
update(v*2, left, mid, pos, val);
else
update(v*2+1, mid+1, right, pos, val);
t[v] = max(t[v*2], t[v*2+1]);
return 0;
}
- Ну ладно, Шарик, раз уж ты функцию написал, слушай. Я тебе дам массив, состоящий из N неотрицательных чисел и множество запросов одного из двух типов: если тип запроса равен единице, то далее будет следовать одно число p, и тебе необходимо найти таких два числа l и r (1 ≤ l ≤ r ≤ n), что функция вызванная следующим образом
get_max(1, 1, n, l, r)
вернет значение равное p, если таких пар несколько, выведи такую, в которой минимально число l, если и таких несколько, выведи из них ту, где минимально r. Если таких пар нет, выведи строку "Error". Если же тип запроса равен двум, то далее следует два числа x, y и необходимо запустить функцию следующим образом
update(1, 1, n, x, y)
Справишься с такой задачей? Можно считать, что в самом начале была вызвана функция
build(1, 1, n)
из предыдущей задачи.
- Попробую, Матроскин.
Входные данные
Первая строка содержит единственное число n (1 ≤ n ≤ 10^6) - количество элементов в массиве. Во второй строке находится n неотрицательных чисел, не превосходящих 10^9 - элементы массива. Далее следует число m (1 ≤ m ≤ 10^5) - количество запросов. И затем m строк, каждая из которых содержит первое число – тип запроса, а далее описание запроса, состоящее из одного или двух чисел.
Выходные данные
Для каждого запроса с типом 1 выведите ответ на задачу.