← 返回题目列表

AtCoder · arc216_b

B. 范围 Mex 总和

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

分数: 700 点

问题陈述

给你一个正整数 N 和整数序列 A = (A_1, A_2, \ldots, A_N)。每个 A_i 满足 -1 \leq A_i \leq N-1,并且对于 1 \leq i < j \leq N,如果 A_i \neq -1 和 A_j \neq -1,那么 A_i \neq A_j.

回答以下问题 Q 次。

  • 给你整数 l, r\ (1 \leq l \leq r \leq N).
    求总和,模 998244353,属于 \mathrm{mex}(\lbrace P_l, P_{l+1}, \ldots, P_r \rbrace) 所有排列 P = (P_1, P_2, \ldots, P_N) of (0, 1, \ldots, N-1) 满意 A_i \neq -1 \implies P_i = A_i.
什么是 \mathrm{mex}(S)? 一套 S 非负整数, \mathrm{mex}(S) 被定义为不包含在中的最小非负整数 S.

约束

  • 1 \leq N \leq 5000
  • 1 \leq Q \leq 5 \times 10^5
  • -1 \leq A_i \leq N-1
  • 对于 1 \leq i < j \leq N,如果 A_i \neq -1 和 A_j \neq -1,那么 A_i \neq A_j.
  • 对于每个查询, 1 \leq l \leq r \leq N.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

l r

输出

输出 Q 行。的 i- 第行应包含以下问题的答案 \mathrm{query}_i.


示例输入 1

3 4
0 -1 -1
1 1
2 2
1 2
1 3

示例输出 1

2
0
3
6

排列 P 满意 A_i \neq -1 \implies P_i = A_i 是 (0, 1, 2) 和 (0, 2, 1)。因此,每个查询的答案计算如下。

  • 第一个查询的答案是 \mathrm{mex}(\lbrace 0 \rbrace) + \mathrm{mex}(\lbrace 0 \rbrace) = 1 + 1 = 2.
  • 第二个查询的答案是 \mathrm{mex}(\lbrace 1 \rbrace) + \mathrm{mex}(\lbrace 2 \rbrace) = 0 + 0 = 0.
  • 第三个查询的答案是 \mathrm{mex}(\lbrace 0, 1 \rbrace) + \mathrm{mex}(\lbrace 0, 2 \rbrace) = 2 + 1 = 3.
  • 第四个查询的答案是 \mathrm{mex}(\lbrace 0, 1, 2 \rbrace) + \mathrm{mex}(\lbrace 0, 2, 1 \rbrace) = 3 + 3 = 6.

示例输入 2

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

示例输出 2

6
8
30

示例输入 3

15 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 15

示例输出 3

612227903