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

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

HotLog


 

Чемпионат по устному счету

(Время: 2 сек. Память: 32 Мб Сложность: 24%)

Председатель жюри чемпионата по устному счету Иван Владимирович Треугольников придумал новое задание для участников чемпионата. Исходно на доске выписывается n целых чисел: a1, a2, ... , an. После этого участник должен выполнять команды двух типов:

  1. Стереть i-е число с доски и записать вместо него число x. То есть, если на доске были записаны числа a1, a2, ... , an, то после выполнения команды числа будут равны: a1, ... , ai−1, x, ai+1, ... , an.
  2. Циклически сдвинуть последовательность чисел на k вправо. То есть, если на доске были записаны числа a1, a2, ... , an, то после выполнения команды числа будут равны: an−k+1, an−k+2, ... , an, a1, a2, ... , an−k.

После выполнения каждой команды участник должен вычислить сумму всех чисел, записанных на доске, и сообщить ее жюри. Чтобы подготовиться проверять ответы участников, членам жюри необходимо самим вычислить требуемые суммы.

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

В первой строке входного файла INPUT.TXT записано целое число n – количество чисел, изначально записанных на доске (2 ≤ n ≤ 105).

Во второй строке через пробел записаны n целых чисел: a1, a2, ... , an – числа, изначально выписанные на доске (−109 ≤ ai ≤ 109).

В третьей строке записано целое число q – количество команд, которые необходимо выполнить (1 ≤ q ≤ 105).

В каждой из следующих q строк записана очередная команда в следующем формате:

  • 1 i x – это означает, что участник должен заменить i-е число последовательности на число x (1 ≤ i ≤ n; −109 ≤ x ≤ 109).
  • 2 k – это означает, что участник должен циклически сдвинуть последовательность чисел на k вправо (1 ≤ k < n).

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

В выходной файл OUTPUT.TXT выведите q строк, в каждой из которых записано одно целое число. В i-й строке должна быть записана сумма чисел на доске после выполнения первых i команд.

Примеры

INPUT.TXTOUTPUT.TXT
16
4 1 2 1 5 3
5
2 3
1 3 10
1 4 4
2 1
1 1 -10
16
23
23
23
11
23
1000000000 1000000000 1000000000
3
1 2 999999999
2 2
1 2 999999999
2999999999
2999999999
2999999998

Пояснение

В первом примере изначально последовательность записанных на доске чисел равна: 4, 1, 2, 1, 5, 3.

После первой команды последовательность циклически сдвигается на 3 элемента вправо. Новая последовательность: 1, 5, 3, 4, 1, 2. Сумма чисел равна: 1 + 5 + 3 + 4 + 1 + 2 = 16.

После второй команды необходимо заменить третий элемент последовательности на число 10. Новая последовательность: 1, 5, 10, 4, 1, 2. Сумма чисел равна: 1 + 5 + 10 + 4 + 1 + 2 = 23.

После третьей команды заменить четвертый элемент на число 4. Так как четвертый элемент уже равен 4, последовательность не изменяется. Сумма чисел также равна 23.

После четвертой команды последовательность циклически сдвигается на 1: 2, 1, 5, 10, 4, 1. Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна: −10, 1, 5, 10, 4, 1. Сумма чисел в итоговой последовательности равна −10 + 1 + 5 + 10 + 4 + 1 = 11.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Чемпионат по устному счету
 B. Прыгающий робот
 C. Треугольная головоломка
 D. Массивы-палиндромы
 E. Новый год в детском саду
 F. Сортировка дробей
 G. Оптические каналы связи
 H. Подарки

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