Задача №3563. Range Variation Query
В начальный момент времени последовательность \(a_n\) задана следующей формулой: \(a_n = n^2 \bmod 12345 + n^3 \bmod 23456\).
Требуется много раз отвечать на запросы следующего вида:
- найти разность между максимальным и минимальным значениями среди элементов \(a_i, a_{i+1}, \ldots, a_j\);
- присвоить элементу \(a_i\) значение \(j\).
Первая строка входного файла содержит натуральное число \(k\) — количество запросов (\(1 \le k \le 100\,000\)). Следующие \(k\) строк содержат запросы, по одному на строке. Запрос номер \(i\) описывается двумя целыми числами \(x_i\), \(y_i\).
Если \(x_i > 0\), то требуется найти разность между максимальным и минимальным значениями среди элементов \(a_{x_i}, \ldots, a_{y_i}\). При этом \(1 \le x_i \le y_i \le 100\,000\).
Если \(x_i < 0\), то требуется присвоить элементу \(a_{|x_i|}\) значение \(y_i\). В этом случае \(-100\,000 \le x_i \le -1\) и \(|y_i| \le 100\,000\).
Для каждого запроса первого типа в выходной файл требуется вывести одну строку, содержащую разность между максимальным и минимальным значениями на соответствующем отрезке.
7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3
34 68 250 234 1