P8120 「RdOI R3.5」RMSQ

给出一个长度为 $m$ 的**排列** $b$ 和一个长度为 $n$ 的**序列** $a$。 如果一个序列 $S$，满足其按位置从左到右依次匹配 $b$ 的一个区间从左到右的位置，那么我们说 $S$ 是一个「优美序列」。 给出 $q$ 次询问。每次询问给出两个整数 $l$ 和 $r$。你需要找到一个 $a$ 的 $[l,r]$ 子区间中的一个最长的满足「优美序列」条件的子序列长度。注意子序列可以不连续。

无

无

### 样例解释 $\mathit{lastans}$ 解密后的询问为： ```plain 1 3 1 4 2 4 2 5 2 6 1 6 ``` ### 数据范围 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{分值} & \bm{{n,m\le}} &\bm{{q\le}} & \bm{{T=}} & \textbf{特殊性质} & \textbf{Subtask 依赖}\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} $$ - 特殊性质 $\textbf{A}$：保证 $a_i,b_i,l,r$ 在数据范围内均匀随机。 对于 $100\%$ 的数据，$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\}$。