Absolute Beauty
Contest: Codeforces Round 910 (Div. 2)
Difficulty rating: 1900
Tags: greedy, math

Kirill has two integer arrays $$$a_1,a_2,\ldots,a_n$$$ and $$$b_1,b_2,\ldots,b_n$$$ of length $$$n$$$. He defines the absolute beauty of the array $$$b$$$ as $$$$$$\sum_{i=1}^{n} |a_i - b_i|.$$$$$$ Here, $$$|x|$$$ denotes the absolute value of $$$x$$$.

Kirill can perform the following operation at most once:

- select two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i < j \leq n$$$) and swap the values of $$$b_i$$$ and $$$b_j$$$.

Help him find the maximum possible absolute beauty of the array $$$b$$$ after performing at most one swap.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) — the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\leq b_i\leq 10^9$$$) — the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output one integer — the maximum possible absolute beauty of the array $$$b$$$ after no more than one swap.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, each of the possible swaps does not change the array $$$b$$$.

In the second test case, the absolute beauty of the array $$$b$$$ without performing the swap is $$$|1-1| + |2-2| = 0$$$. After swapping the first and the second element in the array $$$b$$$, the absolute beauty becomes $$$|1-2| + |2-1| = 2$$$. These are all the possible outcomes, hence the answer is $$$2$$$.

In the third test case, it is optimal for Kirill to not perform the swap. Similarly to the previous test case, the answer is $$$2$$$.

In the fourth test case, no matter what Kirill does, the absolute beauty of $$$b$$$ remains equal to $$$16$$$.

Example input:
6
3
1 3 5
3 3 3
2
1 2
1 2
2
1 2
2 1
4
1 2 3 4
5 6 7 8
10
1 8 2 5 3 5 3 1 1 3
2 9 2 4 8 2 3 5 3 1
3
47326 6958 358653
3587 35863 59474

Example output:
4
2
2
16
31
419045

Editorial:
If $$$a_i > b_i$$$, swap them. Imagine the pairs $$$(a_i,b_i)$$$ as intervals. How can we visualize the problem?
The pair $$$(a_i,b_i)$$$ represents some interval, and $$$|a_i - b_i|$$$ is its length. Let us try to maximize the sum of the intervals' lengths. We present three cases of what a swap does to two arbitrary intervals.
Notice how the sum of the lengths increases only in the first case. We want the distance between the first interval's right endpoint and the second interval's left endpoint to be as large as possible. So we choose integers $$$i$$$ and $$$j$$$ such that $$$i \neq j$$$ and $$$a_j - b_i$$$ is maximized. We add twice the value, if it is positive, to the original absolute beauty. If the value is $$$0$$$ or negative, we simply do nothing.
To quickly find the maximum of $$$a_j - b_i$$$ over all $$$i$$$ and $$$j$$$, we simply find the maximum of $$$a_1,a_2,\ldots a_n$$$ and the minimum of $$$b_1,b_2, \ldots b_n$$$. Subtracting the two extremum values produces the desired result.
How to handle point updates? (change a single value in either $$$a$$$ or $$$b$$$, and print the answer after each query.)