Корневая декомпозиция




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

Task
Time limit: 1000 ms,
Memory limit: 256 Mb

Дан массив a длины n (1 <= n <= 2 * 10^6, 1 <= ai <= 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.

Ввод Вывод
5
1 1 1 1 1
3
? 3
* 2 3 9
? 3
1
9

(с) Брынских А, 2018

Auto CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!
Attach the program source file:
or enter the source code in the language:

Rules for designing programs and a list of errors during automatic task verification
           

Results: