AT_2_stpc2025_2_e.Max Twice Subsequences (Easy)

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。

请你回答 $Q$ 次查询。对于第 $i$ 个查询，给出整数 $L_i,R_i$，请你对 $B=(A_{L_i},A_{L_i+1},\dots,A_{R_i})$ 求解如下问题：

给定正整数序列 $B=(B_1,B_2,\dots,B_{|B|})$。如果存在正整数序列 $C=(C_1,C_2,\dots,C_k)$ 满足 $C$ 作为 $B$ 的非空子序列出现至少两次（形式上，存在正整数 $k$ 和两组下标序列 $(i_1,i_2,\dots,i_k),(j_1,j_2,\dots,j_k)$ 满足以下所有条件，使得 $C$ 被称为好序列）：

• $1\le i_1<i_2<\dots<i_k\le |B|$
• $1\le j_1<j_2<\dots<j_k\le |B|$
• 对于 $p=1,2,\dots,k$，均有 $B_{i_p}=B_{j_p}=C_p$
• 存在某个 $p\ (1 \le p \le k)$ 使得 $i_p\neq j_p$

判断是否存在好序列。如果存在，输出好序列中字典序最大的一个的 滚动哈希。正整数序列 $a=(a_1,\dots,a_n)$ 的 滚动哈希 定义为 $\displaystyle \left(\sum_{i=1}^{n}a_i 3^{i-1}\right)\bmod 998244353$。如果不存在好序列，输出 $-1$。

保证所有查询的 $R_i-L_i+1$ 的总和不超过 $10^7$。

输入如下所示：

$N\ Q$

$A_1\ A_2\ \dots\ A_N$

$L_1\ R_1$

$L_2\ R_2$

$\vdots$

$L_Q\ R_Q$

输出共 $Q$ 行。第 $i$ 行输出对应 $B=(A_{L_i},A_{L_i+1},\dots,A_{R_i})$ 的答案。

样例解释 1

对于第 $1$ 个查询，$B=(3,2,1,2,3)$。作为非空子序列至少出现两次的序列中字典序最大的为 $(3,2,3)$。对于它，可以取两组下标序列分别为 $(1,2,5),(1,4,5)$。

第 $2$ 个查询，$B=(3,2,1)$，不存在至少出现两次的非空子序列。

第 $3$ 个查询，$B=(2,1,2)$，作为非空子序列至少出现两次的最大字典序为 $(2)$。

第 $4$ 个查询，$B=(2,1,2,3)$，作为非空子序列至少出现两次的最大字典序为 $(2,3)$。

数据范围

• 所有输入均为整数。
• $1\le N,Q\le 3\times 10^5$
• $1\le A_i\le N\ (1\le i\le N)$
• $1\le L_i\le R_i\le N\ (1\le i\le Q)$
• $\sum_{i=1}^{Q}(R_i-L_i+1)\le 10^7$

由 ChatGPT 5 翻译