Flip - MarisaOJ: Marisa Online Judge

Flip

Time limit: 1000 ms
Memory limit: 256 MB
Given two arrays $a$ and $b$, each containing $n$ distinct integers. Define an operation where you reverse the elements in a subarray $[l...r]$ and swap the maximum and minimum values in that subarray. Your task is to determine the sequence of operations required to transform array $a$ into array $b$. ### Input - The first line contains an integer $n$. - The second line contains $n$ integers, the array $a$. - The third line contains $n$ integers, the array $b$. ### Output - The first line should contain an integer $q$, the number of operations. - The next $q$ lines should each contain two integers $l$ and $r$, representing the subarray $[l...r]$ to reverse. ### Constraints - $1 \leq a_i, b_i \le n \leq 4096$. - $1 \leq q \leq 3 \times 10^5$. ### Sample Test Input: ``` 4 2 4 3 1 1 2 3 4 ``` Output ``` 4 3 4 2 3 1 2 3 4 ``` ### Subtasks - **Subtask 1 (20% of the points):** $n \leq 100$. - **Subtask 2 (40% of the points):** $n \leq 2048$. - **Subtask 3 (40% of the points):** No additional constraints.