Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Хорошо.
a[i] — баланс ресурса за период i; отрицательный баланс разрешён. ADD вносит поправку за диапазон периодов.
Разработайте систему диапазонной статистики последовательности целых измерений. Нужно изменять целый интервал, присваивать отдельное значение и быстро получать сумму и минимум.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
n — длина от 1 до 100000; элементы индексируются от 0 до n−1.a0 … a(n-1), delta, value — целые входные значения от -1000000000 до 1000000000.l, r — включительные границы интервала, i — индекс элемента.| Команда | Действие | Ответ |
|---|---|---|
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 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
Ввод:
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
Ввод:
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