B - Range Mex Sum 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

正整数 N および整数列 A=(A_1,A_2,\ldots,A_N) が与えられます．A_i は -1 以上 N-1 以下であり，1\leq i\lt 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) が与えられる．
    (0,1,\ldots,N-1) の順列 P=(P_1,P_2,\ldots,P_N) であって，A_i\neq -1\implies P_i=A_i を満たすようなもの全てに対する \mathrm{mex}(\lbrace P_l,P_{l+1}, \ldots,P_r\rbrace) の総和を 998244353 で割った余りを求めよ．
\mathrm{mex}(S) とは 非負整数からなる集合 S に対して，S に含まれない最小の非負整数を \mathrm{mex}(S) と定義します．

制約

  • 1\leq N\leq 5000
  • 1\leq Q\leq 5\times 10^5
  • -1\leq A_i\leq N-1
  • 1\leq i\lt 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

A_i\neq -1\implies P_i=A_i であるような順列 P は (0, 1, 2) と (0, 2, 1) の 2 つです．したがって，各クエリの答えは以下のように求まります．

  • 1 つ目のクエリの答えは \mathrm{mex}(\lbrace 0\rbrace)+\mathrm{mex}(\lbrace 0\rbrace)=1+1=2 です．
  • 2 つ目のクエリの答えは \mathrm{mex}(\lbrace 1\rbrace)+\mathrm{mex}(\lbrace 2\rbrace)=0+0=0 です．
  • 3 つ目のクエリの答えは \mathrm{mex}(\lbrace 0,1\rbrace)+\mathrm{mex}(\lbrace 0,2\rbrace)=2+1=3 です．
  • 4 つ目のクエリの答えは \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

Score : 700 points

Problem Statement

You are given a positive integer N and a sequence of integers A = (A_1, A_2, \ldots, A_N). Each A_i satisfies -1 \leq A_i \leq N-1, and for 1 \leq i < j \leq N, if A_i \neq -1 and A_j \neq -1, then A_i \neq A_j.

Answer the following query Q times.

  • You are given integers l, r\ (1 \leq l \leq r \leq N).
    Find the sum, modulo 998244353, of \mathrm{mex}(\lbrace P_l, P_{l+1}, \ldots, P_r \rbrace) over all permutations P = (P_1, P_2, \ldots, P_N) of (0, 1, \ldots, N-1) satisfying A_i \neq -1 \implies P_i = A_i.
What is \mathrm{mex}(S)? For a set S of non-negative integers, \mathrm{mex}(S) is defined as the smallest non-negative integer not contained in S.

Constraints

  • 1 \leq N \leq 5000
  • 1 \leq Q \leq 5 \times 10^5
  • -1 \leq A_i \leq N-1
  • For 1 \leq i < j \leq N, if A_i \neq -1 and A_j \neq -1, then A_i \neq A_j.
  • For each query, 1 \leq l \leq r \leq N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Each query is given in the following format:

l r

Output

Output Q lines. The i-th line should contain the answer to \mathrm{query}_i.

Sample Input 1

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

Sample Output 1

2
0
3
6

The permutations P satisfying A_i \neq -1 \implies P_i = A_i are (0, 1, 2) and (0, 2, 1). Thus, the answer to each query is computed as follows.

  • The answer to the first query is \mathrm{mex}(\lbrace 0 \rbrace) + \mathrm{mex}(\lbrace 0 \rbrace) = 1 + 1 = 2.
  • The answer to the second query is \mathrm{mex}(\lbrace 1 \rbrace) + \mathrm{mex}(\lbrace 2 \rbrace) = 0 + 0 = 0.
  • The answer to the third query is \mathrm{mex}(\lbrace 0, 1 \rbrace) + \mathrm{mex}(\lbrace 0, 2 \rbrace) = 2 + 1 = 3.
  • The answer to the fourth query is \mathrm{mex}(\lbrace 0, 1, 2 \rbrace) + \mathrm{mex}(\lbrace 0, 2, 1 \rbrace) = 3 + 3 = 6.

Sample Input 2

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

Sample Output 2

6
8
30

Sample Input 3

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

Sample Output 3

612227903