← 返回题目列表

AtCoder · stpc2025_1_e

E. 最多两次子序列

中文机器翻译题面 查看原题

配点 : 100 点

問題文

长度 小于或等于 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) 是 在 B 的非空子序列 当出现超过 2 次时,形式上为正整数 k 和 按字典顺序比较 2 两个下标的序列 当 (i_1,i_2,\dots ,i_k),(j_1,j_2,\dots ,j_k) 存在且满足以下所有条件时, C 该值应乘以好专栏。

  • 1\le i_1\lt i_2\lt \dots \lt i_k\le |B|
  • 1\le j_1\lt j_2\lt \dots \lt 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 。

制約

  • 所有输入均为整数
  • 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)

入力

输入按以下格式给出。

N Q
A_1 A_2 \dots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

Q 行。 i=1,2,\dots, Q 关于 i 线路有问题。 B = (A_{L_i},A_{L_i+1},\dots,A_{R_i}) 。 我们来谈谈第


入力例 1

5 4
3 2 1 2 3
1 5
1 3
2 4
2 5

出力例 1

36
-1
2
11

1 个查询。 B=(3,2,1,2,3) 的非空子序列 当出现超过 2 字典顺序上出现多次的最大的一个是 (3,2,3) 。给这个 2 作为两个下标的序列, 您可以采取 (1,2,5),(1,4,5) 。

2 查询中 给定 B=(3,2,1) 作为非空子序列 任何内容出现的次数不得超过 2 次。

3 查询中 给定 B=(2,1,2) 作为非空子序列 任何内容出现的次数不得超过 2 字典顺序上出现多次的最大的一个是 (2) 。

4 查询中 给定 B=(2,1,2,3) 作为非空子序列 任何内容出现的次数不得超过 2 字典顺序上出现多次的最大的一个是 (2,3) 。


入力例 2

5 1
3 2 1 4 1
1 5

出力例 2

18

入力例 3

10 10
1 4 5 2 5 3 4 2 5 4
1 10
1 9
2 10
1 8
2 9
3 10
1 7
2 8
3 9
4 10

出力例 3

56
20
56
35
20
56
17
35
20
17