CF1093E.Intersection of Permutations

You are given two permutations $a$ and $b$, both consisting of $n$ elements. Permutation of $n$ elements is such a integer sequence that each value from $1$ to $n$ appears exactly once in it.

You are asked to perform two types of queries with them:

• $1~l_a~r_a~l_b~r_b$ — calculate the number of values which appear in both segment $[l_a; r_a]$ of positions in permutation $a$ and segment $[l_b; r_b]$ of positions in permutation $b$;
• $2~x~y$ — swap values on positions $x$ and $y$ in permutation $b$.

Print the answer for each query of the first type.

It is guaranteed that there will be at least one query of the first type in the input.

给你两个长度均为 $n$ 的排列 $a$ 和 $b$。长度为 $n$ 的排列是指一个整数序列，其中每个从 $1$ 到 $n$ 的值恰好出现一次。

你需要对这两个排列执行两种类型的查询：

• $1~l_a~r_a~l_b~r_b$ —— 计算同时出现在排列 $a$ 的位置区间 $[l_a; r_a]$ 和排列 $b$ 的位置区间 $[l_b; r_b]$ 中的数值个数；
• $2~x~y$ —— 交换排列 $b$ 中位置 $x$ 和 $y$ 上的值。

对每个第一类查询，请输出其答案。

保证输入中至少包含一个第一类查询。

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$) — the number of elements in both permutations and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — permutation $a$. It is guaranteed that each value from $1$ to $n$ appears in $a$ exactly once.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) — permutation $b$. It is guaranteed that each value from $1$ to $n$ appears in $b$ exactly once.

Each of the next $m$ lines contains the description of a certain query. These are either:

• $1~l_a~r_a~l_b~r_b$ ($1 \le l_a \le r_a \le n$, $1 \le l_b \le r_b \le n$);
• $2~x~y$ ($1 \le x, y \le n$, $x \ne y$).

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$）—— 分别表示两个排列的元素个数以及查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）—— 排列 $a$。保证 $1$ 到 $n$ 中的每个值在 $a$ 中恰好出现一次。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le n$）—— 排列 $b$。保证 $1$ 到 $n$ 中的每个值在 $b$ 中恰好出现一次。

接下来的 $m$ 行每行描述一个查询，查询类型为以下两种之一：

• $1~l_a~r_a~l_b~r_b$（$1 \le l_a \le r_a \le n$，$1 \le l_b \le r_b \le n$）；
• $2~x~y$（$1 \le x, y \le n$，$x \ne y$）。

Print the answers for the queries of the first type, each answer in the new line — the number of values which appear in both segment $[l_a; r_a]$ of positions in permutation $a$ and segment $[l_b; r_b]$ of positions in permutation $b$.

输出第一类查询的答案，每个答案占一行——即同时出现在排列 $a$ 的位置区间 $[l_a; r_a]$ 和排列 $b$ 的位置区间 $[l_b; r_b]$ 中的数值个数。

Consider the first query of the first example. Values on positions $[1; 2]$ of $a$ are $[5, 1]$ and values on positions $[4; 5]$ of $b$ are $[1, 4]$. Only value $1$ appears in both segments.

After the first swap (the second query) permutation $b$ becomes $[2, 1, 3, 5, 4, 6]$.

After the second swap (the sixth query) permutation $b$ becomes $[5, 1, 3, 2, 4, 6]$.

考虑第一个样例的第一个查询。数组 $a$ 在区间 $[1; 2]$ 上的值为 $[5, 1]$，数组 $b$ 在区间 $[4; 5]$ 上的值为 $[1, 4]$。只有数值 $1$ 同时出现在这两个区间中。

第一次交换（第二个查询）后，排列 $b$ 变为 $[2, 1, 3, 5, 4, 6]$。

第二次交换（第六个查询）后，排列 $b$ 变为 $[5, 1, 3, 2, 4, 6]$。