CF1976E Splittable Permutations

最初，我们有一个长度为 $n$ 的数组，这个数组是一个排列（即长度为 $n$ 的数组，包含 $1$ 到 $n$ 的每个整数且各出现一次）。 我们进行了 $q$ 次操作。在第 $i$ 次操作中，我们进行了如下步骤： - 选择当前拥有的任意一个至少包含 $2$ 个元素的数组； - 将其拆分为两个非空数组（前缀和后缀）； - 记录两个整数 $l_i$ 和 $r_i$，其中 $l_i$ 是拆分后左部分的最大值，$r_i$ 是右部分的最大值； - 将被选择的数组从可用数组池中移除，并将拆分得到的两个部分加入数组池。 例如，假设初始数组为 $[6, 3, 4, 1, 2, 5]$，我们进行了如下操作： 1. 选择数组 $[6, 3, 4, 1, 2, 5]$，将其拆分为 $[6, 3]$ 和 $[4, 1, 2, 5]$。此时记录 $l_1 = 6$，$r_1 = 5$，当前拥有的数组为 $[6, 3]$ 和 $[4, 1, 2, 5]$； 2. 选择数组 $[4, 1, 2, 5]$，将其拆分为 $[4, 1, 2]$ 和 $[5]$。此时记录 $l_2 = 4$，$r_2 = 5$，当前拥有的数组为 $[6, 3]$、$[4, 1, 2]$ 和 $[5]$； 3. 选择数组 $[4, 1, 2]$，将其拆分为 $[4]$ 和 $[1, 2]$。此时记录 $l_3 = 4$，$r_3 = 2$，当前拥有的数组为 $[6, 3]$、$[4]$、$[1, 2]$ 和 $[5]$。 给定两个整数 $n$ 和 $q$，以及两个序列 $[l_1, l_2, \dots, l_q]$ 和 $[r_1, r_2, \dots, r_q]$。如果存在一种长度为 $n$ 的排列，能够通过 $q$ 次操作得到给定的 $[l_1, l_2, \dots, l_q]$ 和 $[r_1, r_2, \dots, r_q]$，则称该排列是“合法”的。 请计算合法排列的数量。

第一行包含两个整数 $n$ 和 $q$（$1 \le q < n \le 3 \cdot 10^5$）。 第二行包含 $q$ 个整数 $l_1, l_2, \dots, l_q$（$1 \le l_i \le n$）。 第三行包含 $q$ 个整数 $r_1, r_2, \dots, r_q$（$1 \le r_i \le n$）。 输入保证：至少存在一个排列可以得到给定的 $[l_1, l_2, \dots, l_q]$ 和 $[r_1, r_2, \dots, r_q]$。

输出一个整数，表示合法排列的数量，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译