Модуль: Корневая декомпозиция


Задача

5 /6


Умножение на отрезке

Теория Нажмите, чтобы прочитать/скрыть


Дана задача, при которой необходимо проводить массовые операции на отрезке и узнавать элемент по индексу.
Массовые операции проводятся как расчёт суммы на отрезке.
Для каждого блока мы храним изменение в этом блоке, и при запросе элемента из этого блока мы учитываем эту информацию.

Задача

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида *, l, r, k (\(1 <= l <= r <= n\), \(0 <= k <10\)) и запросов вида ?, i (\(1 <= i <= n\)).

В первом случае нужно умножить числа на отрезке от l до r включительно на k.

Во втором случае нужно вывести число, стоящее на позиции i.

Элементы нумеруются с 1 до n.

 

Примеры
Входные данные Выходные данные
1
5
1 1 1 1 1
3
? 3
* 2 3 9
? 3
1
9

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

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