e-olimp 695. Range Variation Query

Задача e-olimp 695.

Последовательность [latex]a_{n}[/latex] задается следующей формулой: [latex]a_{n}=n^{2} mod 12345+n^{3} mod 23456[/latex].

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

  • найти разность между максимальным и минимальным значением среди элементов [latex]a_{i},a_{i+1}, …,a_{j}[/latex];
  • присвоить элементу [latex]a_{i}[/latex] значение [latex]j[/latex].

Технические условия.

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

Первая строка содержит натуральное число [latex]k (k\leq 100000)[/latex]  — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_{i},y_{i}[/latex].

Если [latex]x_{i}>0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{x_{i}}…a_{y_{i}}[/latex]. При этом [latex]1\leq x_{i}\leq y_{i}\leq 100000[/latex].

Если [latex]x_{i}<0[/latex], то требуется присвоить элементу [latex]a_{-x_{i}}[/latex] значение[latex]y_{i}[/latex]. При этом[latex]-100000\leq x_{i}\leq 1[/latex] и [latex]\left | y_{i} \right |\leq 100000[/latex].

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

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

Пример.

Пример входных данных Пример выходных данных
7

1 3

2 4

-2 -100

8 9

-3 -101

2 3

34

68

250

234

1

 

Решение.

Так как количество запросов [latex]k\leq 100000[/latex] сначала считаем значение всех элементов последовательности и сохраняем их в массив. Если требуется найти разность между максимумом и минимумом,то находим их проверяя все элементы отрезка и выводим разность. Если требуется заменить  элемент, то заменяем соответствующий элемент последовательности на новый.

Ссылка на засчитанное решение.

Данный код на ideone.

В скором времени будет добавлено более эффективное решение с помощью дерева отрезков.

Недомовний Владислав
Недомовний Владислав

Latest posts by Недомовний Владислав (see all)

One thought on “e-olimp 695. Range Variation Query