Problems
Трое из Простоквашино 2
Трое из Простоквашино 2
\includegraphics{https://static.e-olymp.com/content/c0/c08bdcda603706ed03c55a2f4da4efa0800e0268.jpg}
- \textit{Матроскин, а я дерево отрезков научился строить.}
- \textit{Шарик, лучше бы ты будку новую построил, чем всякую ерунду.}
- \textit{Ну Матроскин, ну я уже и Дяде Федору код показывал, можешь посмотреть в предыдущей задаче, а тебе новую функцию покажу -- изменение.}
\textbf{int update(int v, int left, int right, int pos, int val) \{}
\textbf{if (left == right) \{}
\textbf{t\[v\] = val;}
\textbf{return 0;}
\textbf{\}}
\textbf{int mid = (left+right) / 2;}
\textbf{if (pos <= mid)}
\textbf{update(v*2, left, mid, pos, val);}
\textbf{else}
\textbf{update(v*2+1, mid+1, right, pos, val);}
\textbf{t\[v\] = max(t\[v*2\], t\[v*2+1\]);}
\textbf{return 0;}
\textbf{\}}
- \textit{Ну ладно, Шарик, раз уж ты функцию написал, слушай. Я тебе дам массив, состоящий из }\textbf{N}\textit{ неотрицательных чисел и множество запросов одного из двух типов: если тип запроса равен единице, то далее будет следовать одно число }\textbf{p}\textit{, и тебе необходимо найти таких два числа }\textbf{l }\textit{и }\textbf{r }\textit{(}\textbf{1 }≤ \textbf{l }≤ \textbf{r }≤ \textbf{n}\textit{), что функция вызванная следующим образом}
\textbf{get_max(1, 1, n, l, r)}
\textit{вернет значение равное} \textbf{p}, \textit{если таких пар несколько, выведи такую, в которой минимально число }\textbf{l}, \textit{если и таких несколько, выведи из них ту, где минимально }\textbf{r}. \textit{Если таких пар нет, выведи строку} "\textbf{Error}". \textit{Если же тип запроса равен двум, то далее следует два числа} \textbf{x}, \textbf{y }\textit{и необходимо запустить функцию следующим образом}
\textbf{update(1, 1, n, x, y)}
\textit{Справишься с такой задачей? Можно считать, что в самом начале была вызвана функция}
\textbf{build(1, 1, n)}
\textit{из предыдущей задачи.}
- \textit{Попробую, Матроскин.}
\InputFile
Первая строка содержит единственное число \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^6}) - количество элементов в массиве. Во второй строке находится \textbf{n }неотрицательных чисел, не превосходящих \textbf{10^9} - элементы массива. Далее следует число \textbf{m} (\textbf{1} ≤ \textbf{m }≤ \textbf{10^5}) - количество запросов. И затем \textbf{m }строк, каждая из которых содержит первое число -- тип запроса, а далее описание запроса, состоящее из одного или двух чисел.
\OutputFile
Для каждого запроса с типом \textbf{1 }выведите ответ на задачу.
Input example #1
5 1 2 3 4 5 5 1 2 1 5 2 1 7 1 3 1 6
Output example #1
1 2 1 5 2 3 Error