853. Сережа и массив

У Сережи есть массив, состоящий из n целых чисел a₁, a₂, ..., a_n. Сережа активный мальчик, поэтому сейчас он собирается выполнить m операций. Каждая из этих операций будет иметь один из трех следующих видов:

· Сделать v_i-ый элемент массива равным x_i. Другими словами, выполнить присвоение a_vi = x_i.

· Увеличить каждый элемент массива на y_i. Другими словами, выполнить n присвоений a_i  = a_i +  y_i (1 ≤ i ≤ n).

· Выписать на листок q_i-ый элемент массива. То есть элемент a_qi.

Помогите Сереже, выполните все его операции.

Вход. В первой строке записаны целые числа n, m (1 ≤ n, m ≤ 10⁵). Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) – исходный массив.

Следующие m строк описывают операции, i-ая строка описывает i-ую операцию. Первое число в i-ой строке – целое число t_i (1 ≤  t_i  ≤ 3), которое обозначает тип операции.

· Если t_i  = 1, то далее следуют два целых числа v_i и x_i (1 ≤  v_i  ≤ n, 1 ≤  x_i  ≤ 10⁹).

· Если t_i  = 2, то далее следует целое число y_i (1 ≤  y_i  ≤ 10⁴).

· Если же t_i  = 3, то далее следует целое число q_i (1 ≤  q_i ≤ n).

Выход. Для каждой операции третьего типа выведите значение a_qi. Значения выводите в порядке следования соответствующих запросов во входных данных.

Пример входа 1	Пример выхода 1
5 6 1 2 3 4 5 3 1 2 10 1 1 5 3 1 2 10 3 1	1 5 15
Пример входа 2	Пример выхода 2
10 11 1 2 3 4 5 6 7 8 9 10 3 2 3 9 2 10 3 1 3 10 1 1 10 2 10 2 10 3 1 3 10 3 9	2 9 11 20 30 40 39

РЕШЕНИЕ

обработка массива

Анализ алгоритма

Прочитаем входной массив a. Заведем переменную add, которую инициализируем нулем. При выполнении операции второго типа (увеличение каждого элемента массива на y_i) выполним прибавление add += y_i. Таким образом при отсутствии операций первого типа (присваиваний a_vi = x_i) конечное состояние элемента a_i будет равняться начальному состоянию a_i плюс add. Тогда для сохранения последнего свойства в случае первой операции будем присваивать a_vi = x_i – add.

Пример

Рассмотрим первый пример. Пусть a_i – состояние массива в памяти, a_i’ – реальное состояние массива. Начальное состояние массива:

Поскольку a_i’ = a_i + add, но сначала add = 0, то a_i’ = a_i. То есть изначально физически каждый элемент массива равен самому себе.

Прибавляем 10 ко всем числам массива, add = add + 10 = 10. Имеет место соотношение: a_i’ = a_i + add.

Следующий запрос: a₁’ = 5. Физически следует совершить присваивание

a₁ = 5 – add,

после чего массив примет вид:

При запросе на вывод первого элемента получим a₁’ = a₁ + add = -5 + 10 = 5.

Снова прибавим 10 ко всем числам массива: add = add + 10 = 20.

Первый элемент равен a₁’ = a₁ + add = -5 + 20 = 15.

Реализация алгоритма

Объявим рабочий массив a.

#define MAX 100010

int a[MAX];

Читаем входной массив.

scanf("%d %d",&n,&m);

for(i = 1; i <= n; i++)

scanf("%d",&a[i]);

Инициализируем переменную add.

add = 0;

Последовательно обрабатываем m операций. Тип операции читаем в переменную t.

for(i = 0; i < m; i++)

{

scanf("%d",&t);

Выполняем присвоение a_vi = x_i

if (t == 1)

{

scanf("%d %d",&v,&x);

a[v] = x - add;

} else

Увеличиваем каждый элемент массива на y_i.

if (t == 2)

{

scanf("%d",&y);

add += y;

} else

Выводим q_i-ый элемент массива.

{

scanf("%d",&q);

printf("%d\n",a[q] + add);

}

}