e-olymp
Задачи

Range Variation Query

Range Variation Query

Последовательность an задается следующей формулой: an = n2mod 12345 + n3 mod 23456.

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

  • найти разность между максимальным и минимальным значением среди элементов ai, ai+1, ..., aj;
  • присвоить элементу ai значение j.

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

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

Если xi > 0, то требуется найти разность между максимальным и минимальным значением среди элементов axi...ayi. При этом 1xiyi100 000.

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

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

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

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