P10151 [Ynoi1999] SMV CC-64 "Viper"


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

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.

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

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