#P14217. [2026队测系列]舱位样本的区间缺失值

[2026队测系列]舱位样本的区间缺失值

题目二:

题目背景

在“星港远征计划”中,科研舱需要为一批实验样本分配唯一编号 0,1,…,N−10,1,\ldots,N-1。
不过由于部分记录已经提前锁定,某些舱位上的编号不能改变;还有一些舱位尚未填写,记为 -1。
研究员会不断查询某个连续舱段内样本编号集合的最小缺失值(mex\mathrm{mex}),并希望统计:在所有满足已知记录的完整分配方案中,这个区间的 mex\mathrm{mex} 总和是多少。

题目描述

给定一个正整数 NN 和一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

满足:

  • −1≤Ai≤N−1-1 \le A_i \le N-1
  • 对于任意 1≤i<j≤N1 \le i < j \le N,如果 Ai≠−1A_i \ne -1 且 Aj≠−1A_j \ne -1,那么 Ai≠AjA_i \ne A_j

也就是说,所有不等于 −1-1 的 AiA_i 两两不同。

接下来有 QQ 次询问,每次给出两个整数 l,rl,r(1≤l≤r≤N1 \le l \le r \le N)。

考虑所有满足以下条件的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N):

  • PP 是 (0,1,…,N−1)(0,1,\ldots,N-1) 的一个排列
  • 对于所有 ii,若 Ai≠−1A_i \ne -1,则必须有 Pi=AiP_i=A_i

对于每个这样的排列,取集合

{Pl,Pl+1,…,Pr}\{P_l,P_{l+1},\ldots,P_r\}

并计算它的 mex\mathrm{mex}。

你需要求出:

  • 对所有满足条件的排列 PP
  • 上述区间对应的 mex\mathrm{mex} 值之和
  • 并对 998244353998244353 取模

mex 的定义

对于一个由非负整数组成的集合 SS,mex(S)\mathrm{mex}(S) 表示最小的没有出现在 SS 中的非负整数。


输入格式

输入从标准输入给出,格式如下:

N Q
A1 A2 ... AN
l1 r1
l2 r2
...
lQ rQ

输出格式

输出 QQ 行。

第 ii 行输出第 ii 次询问的答案。


样例 #1

输入

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

输出

2
0
3
6

说明

满足条件的排列只有两个:

  • (0,1,2)(0,1,2)
  • (0,2,1)(0,2,1)

因此:

  • 询问 (1,1)(1,1):mex({0})+mex({0})=1+1=2\mathrm{mex}(\{0\})+\mathrm{mex}(\{0\})=1+1=2
  • 询问 (2,2)(2,2):mex({1})+mex({2})=0+0=0\mathrm{mex}(\{1\})+\mathrm{mex}(\{2\})=0+0=0
  • 询问 (1,2)(1,2):mex({0,1})+mex({0,2})=2+1=3\mathrm{mex}(\{0,1\})+\mathrm{mex}(\{0,2\})=2+1=3
  • 询问 (1,3)(1,3):$\mathrm{mex}(\{0,1,2\})+\mathrm{mex}(\{0,2,1\})=3+3=6$

样例 #2

输入

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

输出

6
8
30

样例 #3

输入

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

输出

612227903

数据范围

  • 1≤N≤50001 \le N \le 5000
  • 1≤Q≤5×1051 \le Q \le 5 \times 10^5
  • −1≤Ai≤N−1-1 \le A_i \le N-1
  • 对于任意 1≤i<j≤N1 \le i < j \le N,如果 Ai≠−1A_i \ne -1 且 Aj≠−1A_j \ne -1,那么 Ai≠AjA_i \ne A_j
  • 每次询问满足 1≤l≤r≤N1 \le l \le r \le N
  • 输入中的所有值均为整数