**Problem Link:** contest, practice

**Difficulty:** Medium

**Pre-requisites:** Maths, Inversions, Fenwick Tree

**Problem:**

We are given two arrays **A[]** and **B[]**. At first, we shuffle **B[]** randomly, then we merge **A[]** and **B[]** into array **C[]** also at random.

Our task is to count the expected number of inversions in **C[]**.

There are **N** elements in **A[]** and **M** elements in **B[]**.

**Explanation:**

Firstly, as far as the expected value has linear properties, we can represent the answer as **AA + BB + AB**.

**AA** is the expected number of inversions between two elements from **A[]**;

**BB** is the expected number of inversions between two elements from **B[]**;

**AB** is the expected number of inversions between two elements, such that one of them is from **A[]** while another is from **B[]**.

Let’s focus on each of this summands and calculate them separately.

**Calculation of AA:**

As far as the elements from **A[]** preserve their order in **C[]**, **AA** is a constant and equals to the number of inversions in **A[]**.

It’s a well-known problem, you can read about that, for example, here: link

**Calculation of BB:**

As far as the elements from **B[]** were shuffled before merging them with **A[]**, they can appear in any order in **C[]**. By using linear properties of the expected value, we can consider each pair of elements from **B[]** separetely.

I.e. we consider a pair **(X, Y)** of integers, assuming that **X** appears in initial, non-shuffled array **B[]** earlier than **Y**. If **X** equals to **Y**, then there is no way for this pair to become an inversion. Otherwise(**X** is different with **Y**) either **X < Y** or **X > Y**. The expected number of inversions of this pair is 1/2.

So, in order to find **BB**, we should count the number of pairs of elements from **B[]**, such that the numbers from each pair don’t equal to each other, and divide it by 2.

Here is a pseudocode, that shows the implementation of the algorithm of calculation **BB**.

```
MEM[] is an array, consisting of 100000 zeroes initially
BB = 0
for i from 1 to M do
begin
BB = BB + MEM[ B[i] ]
MEM[ B[i] ] = MEM[ B[i] ] + 1
end
BB = BB / 2
```

**Calculation of AB:**

We can use the same logic, as we do for calculating **BB**: By using linear properties of the expected value, we can consider each pair of elements, such that one of them is from **A[]** while another is from **B[]**, separetely.

I.e. we consider a pair **(X, Y)** of integers, assuming that **X** is a number from **A[]** while **Y** is a number from **B[]**.

If **X** equals to **Y**, then there is no way for this pair to become an inversion. Otherwise(**X** is different with **Y**) either **X < Y** or **X > Y**.

In case **X < Y** the expected number of inversions of this pair equals to **i / (N + 1)**, where **i** is an index of **X** in array **A[]**.

In case **X > Y** the expected number of inversions of this pair equals to **(N + 1 - i) / (N + 1)**, where **i** is an index of **X** in array **A[]**.

Why it’s so? The point is that the numbers from **A[]** preserve their initial order in **C[]**. Then there are **(N + 1)** different *interesting* positions for **Y** in **C[]**: before **A[1]**, after **A[1]** and before **A[2]**, after **A[2]** and before **A[3]**, …, after **A[N]**. So, we count only positions that lead pair **(X, Y)** to an inversion.

How to count **AB** quickly? We can preprocess numbers from **A[]**, and then for each number from **B[]** count the expected number of inversions of pairs, where the current **B[]** is **Y**.

Here is a pseudocode, that shows the implementation of the algorithm of calculation **AB**.

```
MEM1[] is an array, consisting of 100000 zeroes initially
MEM2[] is an array, consisting of 100000 zeroes initially
AB = 0
for i from 1 to N do
begin
MEM1[ A[i] ] = MEM1[ A[i] ] + i
MEM2[ A[i] ] = MEM2[ A[i] ] + (N + 1 - i)
end
for i from 2 to 100000 do
begin
MEM1[ i ] = MEM1[ i - 1 ] + MEM1[ i ]
end
for i from 99999 to 1 do
begin
MEM2[ i ] = MEM2[ i + 1 ] + MEM2[ i ]
end
for i from 1 to M do
begin
AB = AB + MEM1[ B[i] - 1 ] + MEM2[ B[i] + 1 ]
end
AB = AB / (N + 1)
```

Some words about the pseudocode.

Here **MEM1[i]** denotes the sum of indexes of elements from **A[]**, which are not greater than **i**.

Also **MEM2[I]** denotes the sum of **( N + 1 - index )** of elements from **A[]**, which are not less than **i**.

Please, look carefully through this section one more time if you don’t understand it.

**Setter’s Solution:** link

**Tester’s Solution:** link