P14608 [NWRRC 2025] Infection Investigation

Isaac 是一位专门诊断病毒性疾病的生物学家。病毒通过改变宿主基因组（基因序列）来适应自身需求。Isaac 正在撰写一篇研究基因组中病毒感染的论文。他有一些样本，并请你帮助分析。 为简化问题，我们假设病毒基因组按顺序包含基因 $1, 2, \ldots, n$。宿主基因组是基因 $1, 2, \ldots n$ 的一个排列：按顺序包含基因 $a_1, a_2, \ldots, a_n$。 考虑一个基因组片段 $[l; r]$，包含基因 $a_l, a_{l+1}, \ldots, a_r$。该片段的感染水平通过其与病毒基因组共享的最长子序列的长度来测量。形式化地说，感染水平是最大的 $k$，使得存在 $l \le i_1 < i_2 < \dots < i_k \le r$ 满足不等式 $a_{i_1} < a_{i_2} < \dots < a_{i_{k}}$。 为了分析基因组，Isaac 需要估计 $q$ 个基因组片段的感染水平。为了确保资金，Isaac 只需要近似结果：允许最多 $1.5$ 倍的误差因子。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $q$，分别表示宿主基因组长度和 Isaac 感兴趣的基因组片段数量（$1 \le n, q \le 2 \cdot 10^5$）。 第二行包含 $n$ 个不同的整数 $a_1, a_2, \ldots, a_n$，描述宿主基因组（$1 \le a_i \le n$）。 接下来的 $q$ 行每行包含两个整数 $l$ 和 $r$，表示需要估计感染水平的基因组片段的边界（$1 \le l \le r \le n$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，所有测试用例的 $q$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $q$ 个正整数，表示相应基因组片段的感染水平。 对于每个基因组片段，设你的答案为 $x$，真实答案为 $y$。如果你的答案与真实答案最多相差 $1.5$ 倍，即满足 $\max\left(\frac{x}{y}, \frac{y}{x}\right) \le 1.5$，则你的答案将被视为正确。

翻译由 DeepSeek V3 完成