e-olymp
Məsələlər

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

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

prb4492 - Матроскин, а я дерево отрезков научился строить.

- Шарик, лучше бы ты будку новую построил, чем всякую ерунду.

- Ну Матроскин, ну я уже и Дяде Федору код показывал, можешь посмотреть в предыдущей задаче, а тебе новую функцию покажу – изменение.

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 106) - количество элементов в массиве. Во второй строке находится n неотрицательных чисел, не превосходящих 109 - элементы массива. Далее следует число m (1m 105) - количество запросов. И затем m строк, каждая из которых содержит первое число – тип запроса, а далее описание запроса, состоящее из одного или двух чисел.

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

Для каждого запроса с типом 1 выведите ответ на задачу.

Zaman məhdudiyyəti 10 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri
5
1 2 3 4 5
5
1 2
1 5
2 1 7
1 3
1 6
Çıxış verilənləri
1 2
1 5
2 3
Error
Müəllif Александр Бурков
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года