Background

Problem Description

Given a sequence $a_1,\dots,a_n$ and a permutation $b_1,\dots,b_n$, there are $m$ operations in total:

• Update operation: given $x,y$, change $a_x$ to $y$.
• Query operation: given $l,r,x$, find the longest subsegment $[l',r']$ within $[l,r]$ (i.e. satisfying $l\le l'\le r'\le r$), such that for all $l'\le i<r'$ we have $a_{i+1}=b_{a_i}$, and there exists some $l'\le i\le r'$ with $a_i=x$. You need to output the maximum possible value of $r'-l'+1$ that satisfies the conditions; if no such subsegment exists, output $0$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers representing $a_1,\dots,a_n$.

The third line contains $n$ integers representing $b_1,\dots,b_n$.

The next $m$ lines each contain either $1,x,y$ or $2,l,r,x$, indicating an update operation or a query operation.

All input values are integers.

Output Format

For each query operation, output one line containing the corresponding answer.

8 10
1 4 7 3 8 2 4 7
5 4 8 7 1 6 3 2
2 6 6 2
2 8 8 7
1 4 3
2 6 8 3
2 4 4 3
2 4 4 3
2 6 8 4
2 5 6 2
2 1 8 1
2 1 1 6

1
1
0
1
1
3
2
1
0

Hint

Idea: s_r_f, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Constraints for $100\%$ of the testdata:

$1\le n,m\le 10^6$.

$1\le a_i\le n$.

$1\le b_i\le n$, and all $b_i$ are pairwise distinct.

For update operations, $1\le x,y\le n$.

For query operations, $1\le l\le r\le n$, $1\le x\le n$.

Translated by ChatGPT 5