P10356 [PA 2024] Splatanie ciągów

PA 2024 3A

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Splatanie ciągów](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/spl/)，感谢 Macaronlin 提供翻译** 定义一个数组的稳定性是最长严格单调递增或递减的连续子区间的长度。如数组 $[8,6,1,3,5,7,4,2]$ 的稳定性为 $4$，因为有一个连续递增子区间 $[1,3,5,7]$，并且没有比其更长的严格单调的连续子区间了。 定义 $A\ \text{i}\ B$ 是 $A$ 和 $B$ 按某个方式归并形成的新数组（即新数组可以划分为两个不交叉子序列，且分别是 $A$ 和 $B$），如 $A=[1,2,3],B=[4,5]$，则 $A\ \text{i}\ B$ 可以是 $ [1, 4, 2, 5, 3], [4, 5, 1, 2, 3]$ 或者 $[4, 1, 5, 2, 3]$，但不可能是 $[1,2,3,4,3]$ 或 $[1,2,3,5,4]$。 令 $f(A,B)$ 表示 $A\ \text{i}\ B$ 的最小稳定性。 给你一个长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$。令 $A'$ 是 $A$ 的非空子区间，$B'$ 是 $B$ 的非空子区间。对于所有在区间 $[1,n+m]$ 的整数 $x$，求有多少对 $(A',B')$ 满足 $f(A', B')=x$。答案对 $10^9+7$ 取模。

第一行两个整数 $n$ 和 $m\ (1\le n,m\le 300\,000)$，分别表示 $A$ 数组和 $B$ 数组的长度。 第二行 $n$ 个整数 $A_1,A_2,\ldots,A_n\ (1\le A_i\le n+m)$，表示 $A$ 数组。 第三行 $m$ 个整数 $B_1,B_2,\ldots,B_m\ (1\le B_i\le n+m)$，表示 $B$ 数组。 保证 $A$ 数组和 $B$ 数组中所有整数两两不同。也就是说 $A\ \text{i}\ B$ 一定是 $1$ 到 $n+m$ 的整数的一个排列。

输出一行 $n+m$ 个整数，第 $i$ 个整数表示 满足 $f(A', B')=i$ 的 $(A',B')$ 对数，对 $10^9+7$ 取模。

对于整个区间 $f([1,2,5,7,4],[8,3,6])=2$，如 $[1, 8, 2, 5, 3, 7, 4, 6]$ 的稳定性为 $2$，并且无法找出更小的了。 考虑区间 $[1,2,5,7]$ 和 $[3]$，有 $f([1,2,5,7],[3])=3$，如 $[1,2,5,3,7]$。可以证明对于 $([1,2,5,7],[3])$ 没有比 $3$ 更小稳定性的组合方式了。 考虑区间 $[4]$ 和 $[6]$，有 $f([4],[6])=2$，这两个区间只有两种拼接方式：$[4,6]$ 或 $[6,4]$，并且它们的稳定性都是 $2$。 样例中所有子区间组合的稳定性都不大于 $3$，所以对于 $x\ge 4$ 的情况答案均为 $0$。