====== Вариант 4.13. Скорректированные показания счётчиков ======
[[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Хорошо**.
===== Постановка задачи =====
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