Problem D

The three parts from top to bottom on the left are: non overlapping, partially overlapping, and containing — the three situations. And $$$\Delta$$$ means the contribution will be made to the answer if we exchange $$$b_i$$$ and $$$b_j$$$

Perhaps the text in the picture is a bit blurry: Only situations within the first box will have a positive contribution to the answer. To maximize the contribution, we must find the longest distance beteween two segements. Let's assume that all segements are in the form of $$$a$$$ less than $$$b$$$, if $$$b$$$ less than $$$a$$$, then swap $$$b$$$ and $$$a$$$. Note that this will not affect the answer because the distance won't be changed. So we just need to find the largest $$$a$$$ and the smallest $$$b$$$

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define mark cout<<"-----------> "
void solve()
{
	int n;cin >> n;
	vector<int>a(n + 1);
	for (int i = 1; i <= n; i++)cin >> a[i];
	vector<int>b(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		if (b[i] < a[i])swap(b[i], a[i]);
	}
	int mxa = 0, mnb = 2e9;
	long long sum = 0;
	for (int i = 1; i <= n; i++)
	{
		sum += abs(a[i] - b[i]);
		if (a[i] > mxa)mxa = a[i];
		if (b[i] < mnb)mnb = b[i];
	}
	if (mxa > mnb)sum += 2 * (mxa - mnb);
	//mark;
	cout << sum << '\n';
}

int main()
{
	int t;cin >> t;
	while (t--)
		solve();
}

The time complexity is $$$O(n)$$$.

If there are any errors, please make corrections