Intersection of Permutations
Contest: Educational Codeforces Round 56 (Rated for Div. 2)
Difficulty rating: 2400
Tags: data structures

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.

Input format:
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$$$).

Output format:
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$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
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

Example output:
1
1
1
2
0

Editorial:
At first, time limit was not that tight for the problem. We didn't want any sqrt, bitset or straight up $$$nm$$$ solution to pass (and it's close to none to pass). Jury solution works faster than twice the time limit so we decided 6 seconds is alright.
The task is purely about implementation. You renumerate numbers in permutations so that the queries are (segment of values, segment of positions) and then have the structure to make update in point and sum on rectangle.
Renumeration in my case was making the first permutation into identity one and changing the numbers in second appropriately.
You can choose the structure you want, I'll tell about the one I use when the queries are offline. For online the common technique is having $$$n$$$ BITs, each with treap in it (ordered_set template from pbds is usually enough). For offline you can precalculate the values to fall into each BIT beforehand and do BIT on these values inside. Preprocess all the update and get queries $$$(x, y)$$$, adding $$$y$$$ into all the BITs $$$x$$$ will fall into. Then sort them and leave only unique occurrences.
Overall complexity: $$$O((n + m) \cdot \log^2 n)$$$.