P9540 "AWOI Round 2 C" Array Operations? Array Operations!

You are given two arrays $a, b$ of length $n$. Merge them to obtain an array $c$ of length $2 \times n$. Let the $i$-th element of array $a$ be placed at position $lb_i$ in array $c$ after merging, and the $i$-th element of array $b$ be placed at position $lc_i$ in array $c$ after merging. After merging, it must satisfy $lb_1 < lb_2 < \dots < lb_{n-1} < lb_n$ and $lc_1 < lc_2 < \dots < lc_{n-1} < lc_n$, meaning the relative order of elements within each array remains unchanged. After merging, you need to perform the following operations on array $c$: 1. Toggle operation: Choose an interval $[l, r]$. For each $i \in [l, r]$, if $c_i$ equals $y$, change it to a number different from $y$; otherwise, change it to $y$. 2. Reverse operation: Choose an interval $[l, r]$ and reverse the numbers in this subarray. This operation **must be performed exactly** $z$ times. Output the minimum number of toggle operations needed to make all numbers in array $c$ equal to $y$.

The first line contains three integers $n, y, z$. The second line contains $n$ integers, representing the elements in array $a$. The third line contains $n$ integers, representing the elements in array $b$.

One positive integer, representing the answer.

**[Sample Explanation]** For sample $1$, let $c$ be $\{1, 1, 1, 9, 45, 1, 1, 9, 4, 810\}$. Here, $c_1 = a_1, c_2 = b_1, c_3 = a_2, c_4 = b_2, c_5 = a_3, c_6 = a_4, c_7 = b_3, c_8 = b_4, c_9 = a_5, c_{10} = b_5$. This satisfies the requirements. Then reverse the interval $[4, 7]$, and array $c$ becomes $\{1, 1, 1, 1, 1, 45, 9, 9, 4, 810\}$. Next, perform a toggle operation to change all numbers in $[6, 10]$ into $1$. So only one toggle operation is needed at minimum. It can be proven that no strategy is better than this. **[Constraints]** Please note the special time limit of this problem and use faster I/O. **This problem uses bundled testdata.** | Subtask ID | $n \leqslant$ | Special Property | Score | | -----------: | -----------: | -----------: | -----------: | | $1$ | $5$ | None | $20$ | | $2$ | $10^6$ | $z > n$ | $5$ | | $3$ | $10^6$ | Special Property A | $10$ | | $4$ | $10^6$ | $z = 0$ | $25$ | | $5$ | $10^6$ | None | $40$ | Special Property A: It is guaranteed that the elements in the two arrays are either all equal to $y$, or all not equal to $y$. For all testdata, it is guaranteed that $0 \leqslant y, z \leqslant 10^9$, and all input data are within the `int` range. Translated by ChatGPT 5