====== Вариант 4.12. Баланс ресурсов по периодам ====== [[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Хорошо**. ===== Постановка задачи ===== a[i] — баланс ресурса за период i; отрицательный баланс разрешён. ADD вносит поправку за диапазон периодов. Разработайте систему диапазонной статистики последовательности целых измерений. Нужно изменять целый интервал, присваивать отдельное значение и быстро получать сумму и минимум. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''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.12, 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.12, 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.12, 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.12, created by Ivan Ivanov. Error: STATE OK Error: RANGE Error: RANGE VALUE 9