P6718 [CCO 2018] Flop Sorting

Robert 创建了一道线段树题，题目是： 给定长为 $N$ 的排列 $a_i$，我们规定一个翻牌操作为将一个区间的最小值与最大值交换。现在给定您 $Q$ 个翻牌操作，每次对 $[l,r]$ 执行翻牌操作，求进行 $Q$ 次翻牌操作后的最终序列。 搞好了题目描述，接下来要搞数据了。 现在给定了 $N$，初始序列 $a_i$ 和最终序列，求中间要进行的翻牌操作。

第一行一个整数代表序列长度 $N$。 第二行 $N$ 个整数代表初始序列 $a_i$。 第三行 $N$ 个整数代表最终序列。

首先第一行一个整数 $Q$ 代表要进行的翻牌操作的次数。 接下来 $Q$ 行每行两个整数 $l,r$ 代表对 $[l,r]$ 进行翻牌操作。

#### 样例说明 对于样例 $1$，执行的 $4$ 次翻牌操作为： - 对 $[2,3]$ 进行翻牌操作，交换 $3$ 和 $5$ - 对 $[3,6]$ 进行翻牌操作，交换 $6$ 和 $2$ - 对 $[2,5]$ 进行翻牌操作，交换 $5$ 和 $2$ - 对 $[4,5]$ 进行翻牌操作，交换 $5$ 和 $4$ #### 数据规模与约定 对于 $100\%$ 的数据，$1 \le a_i \le N \le 4096$，$1 \le Q \le 3 \times 10^5$，$1 \le l\le r \le N$。 对于其中 $20\%$ 的数据，$N \le 100$。 对于另外 $40\%$ 的数据，$N \le 2048$。 #### 说明 翻译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [C Flop Shorting](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。