Johnny and New Toy

题意翻译

给定一个序列 $P_1W_1P_2W_2 \cdots W_{n-1}P_n$ 是一个 $1$ 到 $n$ 的排列，$W$ 是一个 $1$ 到 $n−1$ 的排列，定义 $W_0=W_n=0$ 每次可以选择一对 $1 \le l \le r < n$ 满足 $\min_{i=l}^r{W_i}>\max \{W_{l-1},W_{r+1} \}$ 设 $W_{l\cdots r}$ 中的最小值为 $W_m$，把 $P_l$ 到 $P_m$ 组成的段和 $P_{m+1}$ 到 $P_{r+1}$ 组成的段互换位置 这种操作可以进行任意多次，有 $q$ 次修改，每次交换 $P$ 中的两个数，修改后求 $P$ 能达到的逆序对个数最小值 $2 \le n \le 2 \times 10^5,1 \le q \le 5 \times 10^4$，保证两个排列和所有修改随机生成

题目描述

Johnny has a new toy. As you may guess, it is a little bit extraordinary. The toy is a permutation $ P $ of numbers from $ 1 $ to $ n $ , written in one row next to each other. For each $ i $ from $ 1 $ to $ n - 1 $ between $ P_i $ and $ P_{i + 1} $ there is a weight $ W_i $ written, and those weights form a permutation of numbers from $ 1 $ to $ n - 1 $ . There are also extra weights $ W_0 = W_n = 0 $ . The instruction defines subsegment $ [L, R] $ as good if $ W_{L - 1} < W_i $ and $ W_R < W_i $ for any $ i $ in $ \{L, L + 1, \ldots, R - 1\} $ . For such subsegment it also defines $ W_M $ as minimum of set $ \{W_L, W_{L + 1}, \ldots, W_{R - 1}\} $ . Now the fun begins. In one move, the player can choose one of the good subsegments, cut it into $ [L, M] $ and $ [M + 1, R] $ and swap the two parts. More precisely, before one move the chosen subsegment of our toy looks like: $ $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 $ $ and afterwards it looks like this: $ $ 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 $ $ Such a move can be performed multiple times (possibly zero), and the goal is to achieve the minimum number of inversions in $ P $ . </p><p>Johnny's younger sister Megan thinks that the rules are too complicated, so she wants to test her brother by choosing some pair of indices $ X $ and $ Y $ , and swapping $ P\_X $ and $ P\_Y $ ( $ X $ might be equal $ Y $ ). After each sister's swap, Johnny wonders, what is the minimal number of inversions that he can achieve, starting with current $ P $ and making legal moves?</p><p>You can assume that the input is generated <span class="tex-font-style-bf">randomly</span>. $ P $ and $ W$ were chosen independently and equiprobably over all permutations; also, Megan's requests were chosen independently and equiprobably over all pairs of indices.

输入输出格式

输入格式

The first line contains single integer $ n $ $ (2 \leq n \leq 2 \cdot 10^5) $ denoting the length of the toy. The second line contains $ n $ distinct integers $ P_1, P_2, \ldots, P_n $ $ (1 \leq P_i \leq n) $ denoting the initial permutation $ P $ . The third line contains $ n - 1 $ distinct integers $ W_1, W_2, \ldots, W_{n - 1} $ $ (1 \leq W_i \leq n - 1) $ denoting the weights. The fourth line contains single integer $ q $ $ (1 \leq q \leq 5 \cdot 10^4) $ — the number of Megan's swaps. The following $ q $ lines contain two integers $ X $ and $ Y $ $ (1 \leq X, Y \leq n) $ — the indices of elements of $ P $ to swap. The queries aren't independent; after each of them, the permutation is changed.

输出格式

Output $ q $ lines. The $ i $ -th line should contain exactly one integer — the minimum number of inversions in permutation, which can be obtained by starting with the $ P $ after first $ i $ queries and making moves described in the game's instruction.

输入输出样例

输入样例 #1

3
3 2 1
2 1
3
1 3
3 2
3 1

输出样例 #1

0
1
0

输入样例 #2

5
4 3 2 5 1
3 2 1 4
7
5 4
5 2
1 5
2 4
2 4
4 3
3 3

输出样例 #2

3
1
2
1
2
3
3

说明

Consider the first sample. After the first query, $ P $ is sorted, so we already achieved a permutation with no inversions. After the second query, $ P $ is equal to \[ $ 1 $ , $ 3 $ , $ 2 $ \], it has one inversion, it can be proven that it is impossible to achieve $ 0 $ inversions. In the end, $ P $ is equal to \[ $ 2 $ , $ 3 $ , $ 1 $ \]; we can make a move on the whole permutation, as it is a good subsegment itself, which results in $ P $ equal to \[ $ 1 $ , $ 2 $ , $ 3 $ \], which has $ 0 $ inversions.