Johnny and New Toy
Contest: Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!
Difficulty rating: 3300
Tags: data structures, implementation, math

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$$$.

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?

You can assume that the input is generated randomly. $$$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.

Input format:
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 format:
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.

Constraints:
Time limit: 15.0 s
Memory limit: 1024.0 MB

Note:
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.

Example input:
3
3 2 1
2 1
3
1 3
3 2
3 1

Example output:
0
1
0

Example input:
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

Example output:
3
1
2
1
2
3
3

Editorial:
Let us start with an analysis of good subsegments for the fixed permutation. The whole permutation is a good subsegment itself, as $$$W_0 = W_n = 0 < W_k$$$ for any $$$k \in [1, 2, \ldots, n - 1]$$$. If we denote the minimal weight in $$$W_1, \ldots, W_{n - 1}$$$ as $$$W_m$$$, then we can notice that subsegments $$$[1, m]$$$ and $$$[m + 1, n]$$$ contain all good subsegments except the whole permutation. As a result, we can recursively find all good subsegments by recursive calls in $$$[1, m]$$$ and $$$[m + 1, n]$$$. We can view the structure of good subsegments as a binary tree.
Example structure of tree for $$$P = [3, 4, 6, 2, 1, 5]$$$ and $$$W = [5, 2, 3, 1, 4]$$$:
Now we want to analyze the possible moves for players. It turns out that the player's move is equivalent to choosing a vertex of a tree and swapping its left and right subtree. Notice that moves made in different vertices influence disjoint pairs of elements, so in some sense these moves are independent if we are interested only in the number of inversions. This observation allows us to find a simple method for calculating the result. For each vertex, calculate the number of inversions between the left and right subtree. Using these numbers for each vertex, we can find out whether we want to swap its subtrees or not, so the result can be calculated by a simple loop over all vertices.
From randomness of the input, we can deduce that the tree we built has height $$$\mathcal{O}(\log n)$$$. We can calculate the number of inversions easily if in each vertex we keep a structure with elements from permutation contained in that vertex. Such structure must support querying the number of elements smaller than some $$$x$$$. The shortest implementation uses the ordered set, but any BST can do it (segment tree needs some squeezing to fit into ML).
The above solution works fast if there are no queries. We can view each request as two removals and additions of elements. If so, we can notice that each query modifies the number of inversions in at most $$$\mathcal{O}(\log n)$$$ vertices. So all we need to do is update the number of inversions in these vertices and recalculate the global result.
Building a tree and calculating initial number of inversions takes $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n \log^2n)$$$, answering each query cost $$$\mathcal{O}(\log^2 n)$$$, so the final complexity is $$$\mathcal{O}(n \log n + q \log^2 n)$$$.