Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

Задача C. Запросы на перестановке

У вас есть перестановка $p_1, . . . , p_n$ и массив целых чисел $a_1, . . . , a_n$, который изначально заполнен нулями. Вам нужно обработать q запросов одного из трёх типов:

• $1$ $l$ $r$ $x$: для всех $l \leq i \leq r$, добавить $x$ к $a_{p_i}$.

• $2$ $l$ $r$: вычислить и вывести $a_l + a_{l+1} + · · · + a_r$.

• $3$ $a$ $b$: поменять местами $p_a$ и $p_b$.

Формат входного файла

В первой строке записаны два целых числа $n$ и $q$ $(2 \leq n, q \leq 10^5)$ — размер перестановки и количество запросов.

Во второй строке записаны $n$ целых чисел $p_1, . . . , p_n (1 \leq p_i \leq n, p_i \neq p_j$ если $i \neq j)$.

Каждая из следующих $q$ строк содержат описания запросов.

Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса:

$1$ $l$ $r$ $x$ $(1 \leq l \leq r \leq n, 1 \leq x \leq 10^5)$ для запросов первого типа.

$2$ $l$ $r$ $(1 \leq l \leq r \leq n)$ для запросов второго типа.

$3$ $a$ $b$ $(1 \leq a, b \leq n, a \neq b)$ для запросов третьего типа.

Формат выходного файла

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

Система оценки

Примеры

Вход

6 9
4 6 3 1 2 5
1 4 5 3
3 3 5
1 2 3 6
3 3 6
3 2 1
2 1 5
2 1 6
1 1 5 6
2 4 6

Выход

12
18
24