← 返回题目列表

Codeforces · 1093/E

E. 排列的交集

中文机器翻译题面 查看原题

给你两个排列 $$$a$$$ 和 $$$b$$$,两者都由 $$$n$$$ 元素组成。 $$$n$$$ 元素的排列是一个整数序列,从 $$$1$$$ 到 $$$n$$$ 的每个值在其中只出现一次。

您需要使用它们执行两种类型的查询:

- $$$1~l_a~r_a~l_b~r_b$$$ — 计算两个段中出现的值的数量 $$$[l_a; r_a]$$$ 排列 $$$a$$$ 中的位置和段 $$$[l_b; r_b]$$$排列中的位置$$$b$$$;
- $$$2~x~y$$$ — 在排列 $$$b$$$ 中交换​​位置 $$$x$$$ 和 $$$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$$$)。

输出

打印第一类查询的答案,新行中的每个答案 — 两个段中出现的值的数量 $$$[l_a; r_a]$$$ 排列 $$$a$$$ 中的位置和段 $$$[l_b; r_b]$$$ 排列中的位置 $$$b$$$。

示例

输入 #1

6 7
5 1 4 2 3 6
2 5 3 1 4 6
1 1 2 4 5
2 2 4
1 1 2 4 5
1 2 3 3 5
1 1 6 1 2
2 4 1
1 4 4 1 3

输出 #1

1
1
1
2
0

注意

考虑第一个示例的第一个查询。仓位价值 $$$[1; $$$a$$$ 中的 2]$$$ 为 $$$[5, 1]$$$ 以及 $$$[4 位置上的值; $$$b$$$ 中的 5]$$$ 为 $$$[1, 4]$$$。仅值 $$$1$$$ 出现在两个段中。

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

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