P8120 "RdOI R3.5" RMSQ

You are given a **permutation** $b$ of length $m$ and a **sequence** $a$ of length $n$. If a sequence $S$ can be matched, from left to right by positions, to the positions from left to right of some interval of $b$, then we call $S$ a "beautiful sequence". You are given $q$ queries. In each query, two integers $l$ and $r$ are given. You need to find, within the subarray $[l,r]$ of $a$, the maximum length of a subsequence that satisfies the "beautiful sequence" condition. Note that a subsequence does not need to be contiguous.

- The first line contains four integers $m,n,q,T$, where the meanings of $n,m,q$ are as described in the statement, and $T$ indicates whether online processing is forced. - The second line contains $m$ integers $b_1,b_2,\cdots,b_m$. - The third line contains $n$ integers $a_1,a_2,\cdots,a_n$. - The next $q$ lines each contain two integers $l',r'$. If $T=1$, you need to compute the real $l,r$ by bitwise XOR of $l'$ and $r'$ with $\mathit{lastans}$. Here, $\mathit{lastans}$ is defined as the answer to the previous query; if there was no previous query, it is $0$. Otherwise, if $T=0$, then $l=l',r=r'$.

- Output a total of $q$ lines. - On the $i$-th line, output one integer, the answer to the $i$-th query.

### Sample Explanation The queries after decrypting with $\mathit{lastans}$ are: ```plain 1 3 1 4 2 4 2 5 2 6 1 6 ``` ### Constraints $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{Score} & \bm{{n,m\le}} &\bm{{q\le}} & \bm{{T=}} & \textbf{Special Property} & \textbf{Subtask Dependencies}\cr\hline 1 & 10 & 100 & 10^4 & 1 & \textbf{A} & -\cr\hline 2 & 15 & 10^5 & 10^5 & 1 & \textbf{A} & 1\cr\hline 3 & 30 & 3\times 10^5 & 10^6 & 0 & - & -\cr\hline 4 & 45 & 3\times 10^5 & 10^6 & 1 & - & 2,3\cr\hline \end{array} $$ - Special property $\textbf{A}$: it is guaranteed that $a_i,b_i,l,r$ are uniformly random within the constraints. For $100\%$ of the testdata, $1\le l\le r\le n\le 3\times 10^5$, $1\le a_i\le m\le 3\times 10^5$, $1\le q \le 1\times 10^6$, $T \in \{0,1\}$. Translated by ChatGPT 5