题目描述

给你两个长度为 $n$ 的序列 $a$ 和 $b$ ，它们都是由 $1\sim n$ 组成的排列。

即 $a$ 中 $1$ 到 $n$ 的每个数都正好出现一次，$b$ 也是这样。

你需要对它们进行两种类型的查询：

• $1\ l\ r\ x\ y$，查询有多少个数既在 $a_l\sim a_r$ 中出现，又在 $b_x\sim b_y$ 中出现。
• $2\ x\ y$，交换 $b$ 中第 $x$ 个数与第 $y$ 个数。

输入格式

第一行包含两个整数 $n$ 和 $m$，两个排列中的元素个数和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$

接下来的 $m$ 行，每行对应一个询问，格式如题面描述。

输出格式

对于每个第一种查询，输出一行一个整数，为对应的答案。

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
2
0

数据规模与约定

对于 $60\%$ 的数据，保证没有操作 2。

对于 $100\%$ 的数据，$n,m\le 5000$，其他所有数据保证合法。

来源

https://codeforces.com/problemset/problem/1093/E