CF1361F Johnny and New Toy

Johnny 有一个新玩具。你可能已经猜到，这个玩具有点特别。玩具是一个长度为 $n$ 的排列 $P$，由 $1$ 到 $n$ 的数字组成，依次排列在一行上。 对于每个 $i$（$1 \leq i \leq n-1$），在 $P_i$ 和 $P_{i+1}$ 之间写有一个权值 $W_i$，这些权值构成了 $1$ 到 $n-1$ 的一个排列。此外，还有额外的权值 $W_0 = W_n = 0$。 规则定义了一个子区间 $[L, R]$ 是“好”的，当且仅当对于任意 $i \in \{L, L+1, \ldots, R-1\}$，都有 $W_{L-1} < W_i$ 且 $W_R < W_i$。对于这样的子区间，还定义 $W_M$ 为集合 $\{W_L, W_{L+1}, \ldots, W_{R-1}\}$ 的最小值。 现在游戏开始了。在一次操作中，玩家可以选择一个“好”的子区间，将其切分为 $[L, M]$ 和 $[M+1, R]$ 两部分，并交换这两部分。更具体地说，操作前该子区间的结构为： $$ W_{L-1}, P_L, W_L, \ldots, W_{M-1}, P_M, W_M, P_{M+1}, W_{M+1}, \ldots, W_{R-1}, P_R, W_R $$ 操作后变为： $$ W_{L-1}, P_{M+1}, W_{M+1}, \ldots, W_{R-1}, P_R, W_M, P_L, W_L, \ldots, W_{M-1}, P_M, W_R $$ 这样的操作可以执行多次（也可以不执行），目标是让排列 $P$ 的逆序对数量最小。 Johnny 的妹妹 Megan 觉得规则太复杂了，于是她想考考哥哥。她会选择一对下标 $X$ 和 $Y$，并交换 $P_X$ 和 $P_Y$（$X$ 可能等于 $Y$）。每次妹妹交换后，Johnny 都想知道，从当前的 $P$ 出发，经过若干次合法操作后，能得到的最小逆序对数是多少。 你可以假设输入是随机生成的。$P$ 和 $W$ 是独立且等概率的全排列，Megan 的每次询问也是独立且等概率地选择下标对。

第一行包含一个整数 $n$，表示玩具的长度，$2 \leq n \leq 2 \cdot 10^5$。 第二行包含 $n$ 个两两不同的整数 $P_1, P_2, \ldots, P_n$，表示初始排列 $P$，$1 \leq P_i \leq n$。 第三行包含 $n-1$ 个两两不同的整数 $W_1, W_2, \ldots, W_{n-1}$，表示权值，$1 \leq W_i \leq n-1$。 第四行包含一个整数 $q$，表示 Megan 的交换次数，$1 \leq q \leq 5 \cdot 10^4$。 接下来的 $q$ 行，每行包含两个整数 $X$ 和 $Y$，表示要交换 $P_X$ 和 $P_Y$，$1 \leq X, Y \leq n$。每次询问之间是相关的，每次交换后排列都会改变。

输出 $q$ 行，第 $i$ 行输出一个整数，表示在第 $i$ 次询问后，从当前 $P$ 出发，经过若干次合法操作后，能得到的最小逆序对数。

考虑第一个样例。第一次询问后，$P$ 已经有序，因此逆序对数为 $0$。 第二次询问后，$P$ 变为 $[1, 3, 2]$，有一个逆序对，可以证明无法通过操作得到 $0$ 逆序对。 最后，$P$ 变为 $[2, 3, 1]$；我们可以对整个排列进行一次操作（整个区间本身是一个好子区间），结果为 $[1, 2, 3]$，逆序对数为 $0$。 由 ChatGPT 4.1 翻译