分数: 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