P10356 [PA 2024] Weaving Sequences

PA 2024 3A

Define the stability of an array as the length of the longest contiguous subarray that is strictly increasing or strictly decreasing. For example, the stability of the array $[8,6,1,3,5,7,4,2]$ is $4$, because it has a contiguous increasing subarray $[1,3,5,7]$, and there is no longer strictly monotone contiguous subarray. Define $A\ \text{i}\ B$ as a new array formed by merging $A$ and $B$ in some way (that is, the new array can be split into two non-overlapping subsequences, which are exactly $A$ and $B$). For example, if $A=[1,2,3]$ and $B=[4,5]$, then $A\ \text{i}\ B$ can be $[1,4,2,5,3]$, $[4,5,1,2,3]$, or $[4,1,5,2,3]$, but it cannot be $[1,2,3,4,3]$ or $[1,2,3,5,4]$. Let $f(A,B)$ denote the minimum possible stability among all arrays in $A\ \text{i}\ B$. You are given an array $A$ of length $n$ and an array $B$ of length $m$. Let $A'$ be a non-empty contiguous subarray of $A$, and $B'$ be a non-empty contiguous subarray of $B$. For every integer $x$ in the range $[1,n+m]$, compute how many pairs $(A',B')$ satisfy $f(A',B')=x$. Output the answer modulo $10^9+7$.

The first line contains two integers $n$ and $m$ $(1\le n,m\le 3\times 10^5)$, the lengths of arrays $A$ and $B$. The second line contains $n$ integers $A_1,A_2,\ldots,A_n$ $(1\le A_i\le n+m)$, describing array $A$. The third line contains $m$ integers $B_1,B_2,\ldots,B_m$ $(1\le B_i\le n+m)$, describing array $B$. It is guaranteed that all integers in arrays $A$ and $B$ are pairwise distinct. In other words, $A\ \text{i}\ B$ is always a permutation of the integers from $1$ to $n+m$.

Output one line with $n+m$ integers. The $i$-th integer is the number of pairs $(A',B')$ such that $f(A',B')=i$, modulo $10^9+7$.

For the full ranges, $f([1,2,5,7,4],[8,3,6])=2$. For example, the stability of $[1,8,2,5,3,7,4,6]$ is $2$, and it is impossible to make it smaller. Consider the ranges $[1,2,5,7]$ and $[3]$. We have $f([1,2,5,7],[3])=3$, for example $[1,2,5,3,7]$. It can be proven that for $([1,2,5,7],[3])$, no merging method can achieve stability smaller than $3$. Consider the ranges $[4]$ and $[6]$. We have $f([4],[6])=2$. These two ranges have only two ways to interleave: $[4,6]$ or $[6,4]$, and both have stability $2$. In the sample, the stability of every subarray pair is at most $3$, so for $x\ge 4$ the answer is $0$. Translated by ChatGPT 5