409680: GYM103678 C Бернард и запросы на арифметических прогрессиях

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Бернард и запросы на арифметических прогрессияхограничение по времени на тест7 секундограничение по памяти на тест1024 мегабайтавводстандартный вводвыводстандартный вывод

Рудольф подарил Бернарду на День рождения массив из $$$N$$$ чисел: $$$A_1, A_2, ..., A_N$$$. Бернарду очень нравятся арифметические прогрессии, поэтому он придумал $$$Q$$$ запросов на арифметических прогрессиях. Запросы могут быть двух типов:

  • $$$1$$$ $$$i$$$ $$$d$$$ $$$k$$$ $$$v$$$ — прибавить к числам $$$A_i, A_{i + d}, A_{i + 2\cdot d}, ..., A_{i + (k - 1) \cdot d}$$$ число $$$v$$$.
  • $$$2$$$ $$$i$$$ $$$d$$$ $$$k$$$ — найти значение выражения $$$A_i + A_{i + d} + A_{i + 2\cdot d}\,+\,...\,+\,A_{i + (k - 1) \cdot d}$$$.

Помогите Бернарду и выведите ответ на каждый запрос второго типа.

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

Первая строка входных данных содержит два целых числа $$$N$$$ и $$$Q$$$ ($$$1 \le N, Q \le 2\cdot10^5$$$).

Вторая строка содержит $$$N$$$ целых чисел $$$A_1, A_2, ..., A_n$$$ ($$$-10^5 \le A_i \le 10^5$$$).

Затем следуют $$$Q$$$ строк, каждая задает запрос:

  • $$$1$$$ $$$i$$$ $$$d$$$ $$$k$$$ $$$v$$$ ($$$i > 0, k > 0, i + (k-1) \cdot d \le n, -10^5 \le v \le 10^5$$$)
  • $$$2$$$ $$$i$$$ $$$d$$$ $$$k$$$ ($$$i > 0, k > 0, i + (k-1) \cdot d \le n$$$)
Выходные данные

Выведите ответ на каждый запрос второго типа.

Система оценки
ГруппаДоп. ограниченияБаллыТребуемые подзадачиТип проверки
$$$1$$$$$$N, Q \le 1000$$$$$$10$$$Полная
$$$2$$$$$$d = 1$$$ для всех запросов$$$16$$$Полная
$$$3$$$$$$t_j \le t_{j + 1} (0 \le j \le q - 1) $$$$$$20$$$Полная
где $$$t_j$$$ - тип $$$j$$$-го запроса ($$$1$$$ или $$$2$$$)
$$$4$$$$$$d = 1$$$ для запросов 2-го типа$$$24$$$$$$2$$$Полная
$$$5$$$$$$30$$$$$$1-4$$$Полная
ПримерВходные данные
5 5
3 0 -2 1 -6
2 1 3 2
1 2 2 2 4
2 1 3 2
1 3 1 3 -3
2 1 2 3
Выходные данные
4
8
-11

加入题单

上一题 下一题 算法标签: