Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade4:13

Вариант 4.13. Скорректированные показания счётчиков

Постановка задачи

a[i] — показание прибора i; delta — калибровочная поправка. Значения могут быть отрицательными. Диапазоны задаются по номерам приборов.

Разработайте систему диапазонной статистики последовательности целых измерений. Нужно изменять целый интервал, присваивать отдельное значение и быстро получать сумму и минимум.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

  • n — длина от 1 до 100000; элементы индексируются от 0 до n−1.
  • a0 … a(n-1), delta, value — целые входные значения от -1000000000 до 1000000000.
  • l, r — включительные границы интервала, i — индекс элемента.
  • До INIT данные не инициализированы.

Операции

Команда Действие Ответ
INIT n a0 … a(n-1) Создать последовательность; повторный INIT полностью заменяет её. OK
ADD l r delta Прибавить delta ко всем значениям с индексами от l до r включительно. OK
SET i value Заменить текущее значение в позиции i. OK
SUM l r Получить сумму значений на интервале. VALUE sum
MIN l r Получить минимальное значение на интервале. VALUE minimum
GET i Получить текущее значение. VALUE value

Правила выполнения и ошибки

Требуется 0 ≤ l ≤ r < n и 0 ≤ i < n; иначе Error: RANGE. До INIT все остальные команды после синтаксических/статических проверок возвращают Error: STATE. SET учитывает все ранее выполненные ADD и заменяет полученное значение. Результаты обновлений и суммы могут превышать диапазон входного value. Входные сценарии гарантируют представимость каждого промежуточного значения и каждой запрашиваемой суммы знаковым 64-битным целым; проверять переполнение и вводить дополнительную ошибку не нужно. В INIT сначала проверяется n, затем число элементов.

Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.

Требования к эффективности

INIT — O(n); ADD, SET, SUM, MIN, GET — O(log(n+2)) в худшем случае. Память — O(n). Диапазонное изменение не должно требовать обхода всех его элементов.

В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.

Формат ввода и вывода

Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:

Course work for option 4.13, created by Ivan Ivanov.

Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.

Примеры

Пример 1. Диапазонное изменение и присваивание

Ввод:

1
6
INIT 3 1 2 3
ADD 0 2 5
SET 1 0
SUM 0 2
MIN 0 2
GET 2

Вывод:

Course work for option 4.13, created by Ivan Ivanov.
OK
OK
OK
VALUE 14
VALUE 0
VALUE 8

Пример 2. Один элемент и переинициализация

Ввод:

1
5
INIT 1 -2
ADD 0 0 -3
SUM 0 0
INIT 1 7
MIN 0 0

Вывод:

Course work for option 4.13, created by Ivan Ivanov.
OK
OK
VALUE -5
OK
VALUE 7

Пример 3. Ошибка не меняет значения

Ввод:

1
5
SUM 0 0
INIT 2 4 5
ADD 1 0 7
SET 2 8
SUM 0 1

Вывод:

Course work for option 4.13, created by Ivan Ivanov.
Error: STATE
OK
Error: RANGE
Error: RANGE
VALUE 9
courses/algorithms_structures/cw_2026/grade4/13.txt · Последнее изменение: — 127.0.0.1