P8415 [THUPC 2022 Finals] pmrmscxip

Given a sequence $a_1,\dots,a_n$ and a permutation $b_1,\dots,b_n$, there are $m$ operations in total: - Modify operation: given $x,y$, change $a_x$ to $y$. - Query operation: given $l,r,x$, find the longest sub-interval $[l',r']$ within $[l,r]$ (i.e., satisfying $l\le l'\le r'\le r$) such that for all $l'\le i

The first line contains two integers $n,m$. The second line contains $n$ integers, representing $a_1,\dots,a_n$ in order. The third line contains $n$ integers, representing $b_1,\dots,b_n$ in order. The next $m$ lines each contain either $1,x,y$ or $2,l,r,x$, indicating one modify operation or one query operation. All input values are integers.

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

Constraints: $1\le n,m\le 10^6$. $1\le a_i\le n$. $1\le b_i\le n$, and all $b_i$ are distinct. For modify 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