Олимпиадный тренинг

Задача . F. Прыжки по массиву

Вам задан массив целых чисел $a$ размера $n$ и перестановка $p$ размера $n$. К вам приходят $q$ запросов трех типов:

Даны числа $l$ и $r$. Требуется посчитать сумму чисел массива $a$ на отрезке c $l$ по $r$: $\sum\limits_{i=l}^{r} a_i$.
Даны числа $v$ и $x$. Давайте представим $p$ в виде ориентированного графа, у которого $n$ вершин и $n$ рёбер $i \to p_i$. Пусть $C$ — это множество вершин, которые достижимы из $v$ в графе. Требуется прибавить число $x$ ко всем $a_u$ таким, что $u$ лежит в $C$.
Даны индексы $i$ и $j$. Вам нужно поменять местами значения $p_i$ и $p_j$.

$\text{[math]}$ Граф, получаемый из перестановки $[2, 3, 1, 5, 4]$.

От вас требуется вывести ответы на все запросы $1$ вида.

Входные данные

В первой строке находится единственное целое число $n$ ($1 \le n \le 2 \cdot 10^5$) — размер массива и перестановки.

Во второй строке входных данных находится $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($-10^8 \le a_i \le 10^8$).

В третьей строке входных данных находится $n$ различных целых чисел $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$).

В четвертой строке находится единственное целое число $q$ — количество запросов ($1 \le q \le 2 \cdot 10^5$).

В следующих $q$ строках заданы запросы. В $i$-й строке находится целое число $t_i$ ($1 \le t_i \le 3$) — тип запроса.

Если $t_i = 1$, то в $i$-й строке заданы еще два целых числа: $l$, $r$ ($1 \le l \le r \le n$).
Если $t_i = 2$, то в $i$-й строке заданы еще два целых числа: $v$, $x$ ($1 \le v \le n$, $-10^8 \le x \le 10^8$).
Если $t_i = 3$, то в $i$-й строке заданы еще два целых числа: $i$, $j$ ($1 \le i, j \le n$).

Выходные данные

Для каждого запроса первого типа выведите единственное целое число — ответ на запрос.

Примечание

Рассмотрим первый тест.

$\text{[math]}$ Граф, получаемый из изначальной перестановки.

В первом тесте $6$ запросов.

Сумма на отрезке с $1$ по $5$ это $a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 3 + 0 = 13$.
Из вершины $1$ достижимы вершины $\{1, 2, 3\}$. Получается, что после этого запроса массив $a$ будет выглядеть так: $[7, 10, -4, 3, 0]$.
Сумма на отрезке с $1$ по $5$ это $a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 3 + 0 = 16$.
После запроса $p = [4, 3, 1, 5, 2]$. $\text{[math]}$ Граф, получаемый из перестановки после четвёртого запроса.
Из вершины $2$ достижимы вершины $\{1, 2, 3, 4, 5\}$. Получается, что после этого запроса массив $a$ будет выглядеть так: $[6, 9, -5, 2, -1]$.
Сумма на отрезке с $1$ по $5$ это $a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 2 + (-1) = 11$.

	Кол-во
С++ Mingw-w64	5

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Нет