eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Range Variation Query

Range Variation Query

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Последовательность a_n задается следующей формулой: a_n = n^2mod 12345 + n^3 mod 23456.

Требуется много раз отвечать на запросы следующего вида:

  • найти разность между максимальным и минимальным значением среди элементов a_i, a_{i+1}, ..., a_j;

  • присвоить элементу a_i значение j.

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

Первая строка содержит натуральное число k (k100 000) - количество запросов. Следующие k строк содержат запросы, по одному в строке. Запрос номер i описывается двумя целыми числами x_i, y_i.

Если x_i > 0, то требуется найти разность между максимальным и минимальным значением среди элементов a_xi...a_yi. При этом 1x_iy_i100 000.

Если x_i < 0, то требуется присвоить элементу a_{-xi} значение y_i. При этом -100 000x_i-1 и |y_i| ≤ 100 000.

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

Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.

Пример

Входные данные #1
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
Выходные данные #1
34
68
250
234
1
Автор В.Гольдштейн
Источник Зимние сборы в Харькове 2010 День 2