PermutationForces II
Contest: Codeforces Round 803 (Div. 2)
Difficulty rating: 2300
Tags: brute force, combinatorics, greedy, sortings, trees, two pointers

You are given a permutation $$$a$$$ of length $$$n$$$. Recall that permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order.

You have a strength of $$$s$$$ and perform $$$n$$$ moves on the permutation $$$a$$$. The $$$i$$$-th move consists of the following:

- Pick two integers $$$x$$$ and $$$y$$$ such that $$$i \leq x \leq y \leq \min(i+s,n)$$$, and swap the positions of the integers $$$x$$$ and $$$y$$$ in the permutation $$$a$$$. Note that you can select $$$x=y$$$ in the operation, in which case no swap will occur.

You want to turn $$$a$$$ into another permutation $$$b$$$ after $$$n$$$ moves. However, some elements of $$$b$$$ are missing and are replaced with $$$-1$$$ instead. Count the number of ways to replace each $$$-1$$$ in $$$b$$$ with some integer from $$$1$$$ to $$$n$$$ so that $$$b$$$ is a permutation and it is possible to turn $$$a$$$ into $$$b$$$ with a strength of $$$s$$$.

Since the answer can be large, output it modulo $$$998\,244\,353$$$.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$s$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s \leq n$$$) — the size of the permutation and your strength, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of $$$a$$$. All elements of $$$a$$$ are distinct.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$ or $$$b_i = -1$$$) — the elements of $$$b$$$. All elements of $$$b$$$ that are not equal to $$$-1$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of ways to fill up the permutation $$$b$$$ so that it is possible to turn $$$a$$$ into $$$b$$$ using a strength of $$$s$$$, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$a=[2,1,3]$$$. There are two possible ways to fill out the $$$-1$$$s in $$$b$$$ to make it a permutation: $$$[3,1,2]$$$ or $$$[3,2,1]$$$. We can make $$$a$$$ into $$$[3,1,2]$$$ with a strength of $$$1$$$ as follows: $$$$$$[2,1,3] \xrightarrow[x=1,\,y=1]{} [2,1,3] \xrightarrow[x=2,\,y=3]{} [3,1,2] \xrightarrow[x=3,\,y=3]{} [3,1,2].$$$$$$ It can be proven that it is impossible to make $$$[2,1,3]$$$ into $$$[3,2,1]$$$ with a strength of $$$1$$$. Thus only one permutation $$$b$$$ satisfies the constraints, so the answer is $$$1$$$.

In the second test case, $$$a$$$ and $$$b$$$ the same as the previous test case, but we now have a strength of $$$2$$$. We can make $$$a$$$ into $$$[3,2,1]$$$ with a strength of $$$2$$$ as follows: $$$$$$[2,1,3] \xrightarrow[x=1,\,y=3]{} [2,3,1] \xrightarrow[x=2,\,y=3]{} [3,2,1] \xrightarrow[x=3,\,y=3]{} [3,2,1].$$$$$$ We can still make $$$a$$$ into $$$[3,1,2]$$$ using a strength of $$$1$$$ as shown in the previous test case, so the answer is $$$2$$$.

In the third test case, there is only one permutation $$$b$$$. It can be shown that it is impossible to turn $$$a$$$ into $$$b$$$, so the answer is $$$0$$$.

Example input:
6
3 1
2 1 3
3 -1 -1
3 2
2 1 3
3 -1 -1
4 1
1 4 3 2
4 3 1 2
6 4
4 2 6 3 1 5
6 1 5 -1 3 -1
7 4
1 3 6 2 7 4 5
2 5 -1 -1 -1 4 -1
14 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Example output:
1
2
0
2
12
331032489

Editorial:
Suppose that we know the elements of $$$b$$$. We claim that the minimum strength needed is $$$\max_{i=1}^n a_i - b_i$$$. Let's prove it.
Proof. For simplicity let's sort the elements of $$$b$$$ from $$$1$$$ to $$$n$$$, and rearrange the corresponding elements of $$$a$$$ in the same way. In other words, we only need to turn this new array $$$a$$$ into the identity $$$[1, 2, \dots, n]$$$.
First note that on the $$$i$$$-th operation, we need to move the number $$$i$$$ to the correct position. This is because of the format of the operations; in any future operation, $$$i$$$ will not be in the given range, so it is required to move $$$i$$$ in the current operation.
Let's look at the number $$$1$$$. If $$$a_1 = 1$$$, then we don't need any strength. Otherwise, we need $$$a_i - 1$$$ strength to swap $$$1$$$ and $$$a_i$$$. Afterwards, we can essentially ignore $$$1$$$ for the rest of the operations, since there is no need to move it again.
In general, there are two cases for when we need to move $$$i$$$ to its correct place:
• $$$a_i \geq i$$$. In this case, we'll never move $$$a_i$$$ until the $$$i$$$-th operation, where we swap $$$i$$$ and $$$a_i$$$. We need a strength of $$$a_i - i$$$ for that. This is necessary.
• $$$a_i < i$$$. In this case, we will swap $$$a_i$$$ in an earlier operation (since $$$a_i < i$$$, so we must swap it to its correct place in the $$$a_i$$$-th operation). If we again end up with some smaller number, we will need to swap that before $$$i$$$, and so on. Suppose that after some time, the current element $$$a_i$$$ in the $$$i$$$-th position is at least $$$i$$$. Then this element must have been swapped with some other element smaller than $$$i$$$ (since we only perform swaps with elements smaller than $$$i$$$ before the $$$i$$$-th operation). In particular, this element originally started somewhere to the left of $$$i$$$, say at position $$$j < i$$$. Then in the strength calculation, we counted $$$a_i - j$$$, which is more than $$$a_i - i$$$, i.e. more than we actually need to swap $$$i$$$ and $$$a_i$$$. This is sufficient.
Hence we only need to check the inequality $$$s \geq a_i - b_i$$$ for all $$$i$$$. Now we proceed to the counting part.
Rewrite this as $$$a_i - s \leq b_i$$$. Suppose that $$$k$$$ values of $$$b_i$$$ are missing. Call them $$$[m_1, \dots, m_k]$$$ in increasing order. Then note that if some element of $$$m$$$ satisfies this inequality, all larger elements of $$$m$$$ will. In other words, for each $$$a_i$$$ whose corresponding element of $$$b$$$ is missing, some suffix of $$$[m_1, \dots, m_k]$$$ will work. We can simply binary search to find this suffix for each $$$a_i$$$. Let $$$l_i$$$ denote the length of this suffix.
Afterwards, we need to count the number of ways to assign each missing element to an $$$a_i$$$. Process the elements greedily, from the $$$a_i$$$ with the fewest choices to the one with the most (that is, the largest $$$a_i$$$ to the smallest). The first $$$a_i$$$ has $$$l_i$$$ choices, the second $$$l_i - 1$$$ (one element of $$$m$$$ was already taken), the third $$$l_i - 2$$$, and so on. We can compute this product straightforwardly.
The time complexity is $$$\mathcal{O}(n \log n)$$$.