P9055 [集训队互测 2021] 数列重排

dottle bot。

定义一个数列区间的 $\textrm{mex}$ 为区间中最小的没有出现过的自然数，定义一个数列的价值为其中 $\textrm{mex}\geq k$ 的区间数量。 给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$，令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值，对于每一个 $k\in [l,r]$，求出 $f(k)$。 令 $a_i$ 表示数字 $i$ 出现的次数，保证存在正整数 $X$，使得 $\forall i\le m-1,a_i\in \{X,X+1\}$。

无

无

#### 样例 1 解释 在样例给出的数列中，有 $3$ 个 $0$ 和 $2$ 个 $1$，任意排列 $f(0)$ 均为 $15$，排列为 $\textrm{01010}$ 时 $f(1)$ 有最大值 $13$，答案为： $$ \displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034 $$ #### 数据范围 - Subtask 1（5 points）：$n,m\leq 9$。 - Subtask 2（15 points）：$n,m\leq 200$。 - Subtask 3（15 points）：$n,m\leq 5\times 10^3$。 - Subtask 4（5 points）：$m\leq 2$，$l=0$，$r=1$。 - Subtask 5（10 points）：$m\leq 10^6$，$l=m$，$r=m$。 - Subtask 6（10 points）：$m\leq 10^6$，$X=1$，$s_i=0$。 - Subtask 7（15 points）：$m\leq 10^6$，$r-l+1\leq 10^4$。 - Subtask 8（15 points）：$m\leq 2\times 10^6$。 - Subtask 9（10 points）：无特殊限制。 对于所有数据，满足 $n\leq 10^9$，$m\leq 10^7$，$0\leq l\leq r\leq m$，$X\geq 1$。