Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Простые операции над массивом

(Время: 1 сек. Память: 16 Мб Сложность: 23%)

Задан массив a[1..n] из n неотрицательных целых чисел. Необходимо реализовать следующие операции над ним:

  • get(i) – извлечение элемента с номером i;
  • update(l,r,x) – присвоение значения x всем элементам подмассива a[l..r];
  • add(l,r,x) – увеличение всех элементов a[l..r] на x;
  • rsq(l,r) – вычисление суммы всех элементов a[l..r], т.е. значения a[l]+a[l+1]+…+a[r];
  • rmq(l,r) – вычисление минимального элемента среди всех значений a[l..r].

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

Первая строка входного файла INPUT.TXT содержит число n – размер массива. Во второй строке записаны n целых неотрицательных чисел – элементы массива. Третья строка содержит натуральное число m – количество запросов. Следующие m строк содержат запросы в формате, представленном в примере. Все числа во входных данных не превосходят 1000.

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

В выходной файл OUTPUT.TXT для запросов get, rsq и rmq выведите результат в отдельной строке в порядке их следования.

Пример

INPUT.TXTOUTPUT.TXT
110
1 2 3 4 5 6 7 8 9 10
5
rsq 1 10
update 5 6 2
rmq 3 9
add 2 8 3
get 7
55
2
10

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Статические RSQ и RMQ
 Sqrt-декомпозиция
 Дерево Фенвика
 Дерево отрезков
 A. Простые операции над массивом
 B. Суммы на отрезках
 C. Суммы в прямоугольнике
 D. Прямоугольник
 E. Суммы на отрезках - 2
 F. Произведения на отрезках
 G. Минимумы на отрезках
 H. Минимумы на отрезках - 2
 I. Охрана
 J. Минимумы в прямоугольнике
 K. Пирамида

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru