Троє з Простоквашино 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) – кількість запитів. І потім М рядків, кожен з яких містить перше число – тип запиту, а далі опис запиту, який складається з одного чи двох чисел.
Вихідні дані
Для кожного запиту з типом 1 виведіть відповідь до задачі.