Module: Root decomposition


Problem

5 /6


Multiplication on a segment

Theory Click to read/hide

A task is given in which it is necessary to carry out bulk operations on a segment and recognize an element by index.
Mass operations are carried out as a sum calculation on a segment.
For each block, we store the change in that block, and when requesting an element from that block, we take that information into account.

Problem

Given an array a of length n (\(1 <= n <= 2 \ cdot 10^6\), \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like *, l, r, k (\(1 <= l <= r < = n\), \(0 <= k <10\)) and queries like ?, i (\(1 <= i <= n\)).

In the first case, you need to multiply the numbers in the segment from l to r inclusive by k.

In the second case, print the number at position i.

Elements are numbered from 1 to n.

 

Examples
# Input Output
1
5
1 1 1 1 1
3
? 3
* 2 3 9
? 3
1
9