K - Median of subsequence 2
問題文
長さ $M$ の数列 $B$ の中央値を、 $B$ を昇順ソートした数列における $\left\lfloor\frac{M+1}{2}\right\rfloor$ 番目の値とします。例えば、 $(3,1,4)$ の中央値は $3$ 、 $(2,7,1,8)$ の中央値は $2$ 、 $(1)$ の中央値は $1$ です。
正整数 $N$ 、長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。 これに対して $Q$ 個の問題を解いてください。 $i$ 番目の問題では整数 $L_i, R_i, X_i$ が与えられるので、以下の問題を解いてください。
整数列 $(A_{L_i}, A_{L_i+1}, \dots ,A_{R_i})$ の空でない連続するとは限らない部分列であって、中央値がちょうど $X_i$ になるものの数を $998244353$ で割った余りを求めてください。ただし、ある 2 つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
制約
- $1\le N\le 2\times 10^5$
- $1\le Q\le 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)$
- $1\le X_i\le N \ (1\le i\le Q)$
- 入力はすべて整数
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($50$ 点)
- $Q\le 10, N\le 18$
- ($150$ 点)
- $Q\le 10$
- ($500$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_Q$ $R_Q$ $X_Q$
出力
$Q$ 行出力せよ。 $i$ 行目には $i$ 番目の問題の答えを出力せよ。
5 3
3 1 4 1 5
1 5 3
2 4 3
5 5 5
10
0
1
1番目の問題について、数列 $(A_1,A_2,A_3,A_4,A_5)$ の部分列のうち、
$(A_1), (A_1,A_3),(A_1,A_5),(A_1,A_2,A_3),(A_1,A_2,A_5),(A_1,A_3,A_4),$
$(A_1,A_4,A_5),(A_1,A_2,A_3,A_5),(A_1,A_3,A_4,A_5),(A_1,A_2,A_3,A_4,A_5)$ の $10$ 個が条件を満たします。
例えば、 $(A_1,A_3,A_4,A_5)=(3,4,1,5)$ は長さ $4$ の数列であり、昇順ソートすると $(1,3,4,5)$ となりますが、その $\lfloor\frac{4+1}{2}\rfloor$ 番目の値は $3$ なので条件を満たしている部分列です。
2番目の問題について、数列 $(A_2,A_3,A_4)$ の部分列であって、中央値が $3$ であるものは存在しません。
この入力は部分点 1., 2., 3. の制約を満たします。
10 10
10 10 10 10 10 10 10 10 10 10
1 1 10
1 2 10
1 3 10
1 4 10
1 5 10
1 6 10
1 7 10
1 8 10
1 9 10
1 10 10
1
3
7
15
31
63
127
255
511
1023
この入力は部分点 1., 2., 3. の制約を満たします。