eolymp
Задачі

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