Олимпиадный тренинг

Задача . E1. Задание на лето


Задача

Темы: Перебор Структуры данных *1500

К своим трем годам Умный Бобер в совершенстве овладел всеми арифметическими операциями, а от своего учителя по математике одаренный ученик получил следующее домашнее задание на лето:

Дана последовательность целых чисел a1, a2, ..., an. Необходимо последовательно произвести над ней m операций следующего вида:

  1. Для заданных чисел xi и vi присвоить элементу axi значение vi.
  2. Для заданных чисел li и ri необходимо вычислить сумму , где f0 = f1 = 1 и при i ≥ 2: fi = fi - 1 + fi - 2.
  3. Для тройки чисел li ri di необходимо для всех x (li ≤ x ≤ ri) увеличить значение ax на di.

Этим летом Умный Бобер решил отправиться в тур по великим озерам Канады, потому просит Вас помочь ему в решении данной задачи.

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

Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество чисел в последовательности и количество операций соответственно. Вторая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 105). Далее идет m строк, каждая из которых описывает операцию. Каждый строка начинается с целого числа ti (1 ≤ ti ≤ 3) — тип операции:

  • если ti = 1, то далее идет два целых числа xi vi (1 ≤ xi ≤ n, 0 ≤ vi ≤ 105);
  • если ti = 2, то далее идет два целых числа li ri (1 ≤ li ≤ ri ≤ n);
  • если ti = 3, то далее идет три целых числа li ri di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 105).

Ограничения на входные данные для получения 30 баллов (подзадача E1):

  • Гарантируется, что n не превышает 100, m не превышает 10000 и не будет запросов 3-го типа.

Ограничения на входные данные для получения 70 баллов (подзадачи E1+E2):

  • Гарантируется, что будут запросы только 1-го и 2-го типа.

Ограничения на входные данные для получения 100 баллов (подзадачи E1+E2+E3):

  • Дополнительные ограничения отсутствуют.
Выходные данные

Для каждого запроса второго типа выведите вычисленную сумму по модулю 1000000000 (109).


Примеры
№Входные данныеВыходные данные
1 5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5 
12
32
8
50
2 5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5 
12
45

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет