第一部分：暴力思路与职位固定性分析

暴力思路

我们首先一起来想一个暴力思路。

暴力怎么做？很简单，依次枚举每一个面试者 $i$，如果 $i$ 没有来面试，那么公司对于剩下的人一个一个按照规则聘用，公司的能力值是多少。时间复杂度 $O((n + m)^2)$。

职位固定性观察

在暴力的过程中可以观察到，总有那么一些面试者，无论谁不来面试，只要不来面试的不是这个人，这个人的职位就是固定的，一定是程序员和测试员中的一个。

职位非固定条件分析

现在我们来考虑什么人的职位不是固定的。在考虑这个之前，我们先来考虑对于第 $i$ 个面试者，如果面试者 $j$ 来与不来能够影响面试者 $i$ 的职位，$j$ 与 $i$ 应该满足什么样的关系。

必要条件

首先，我们要知道面试是按照面试者来的顺序的。如果 $j$ 在 $i$ 之后才来，也即 $j > i$，那么 $j$ 来与不来都是不会影响 $i$ 的职位的，毕竟 $i$ 之前的人是没有变的，面试到 $i$ 时的状态也是没有变的。

因此，我们得到了一个结论：如果一个面试者 $j$ 来与不来能够影响面试者 $i$ 所处职位，那么 $j$ 在 $i$ 之前，也就是 $j < i$。

充分必要条件分析

我们假设 $a_i > b_i$。如果 $j < i$ 并且 $j$ 没来，然后 $i$ 的职位改变了，显而易见 $i$ 只能是从测试员变成程序员。很好理解，原来 $i$ 是可以被聘为程序员的，但是因为程序员人满了，只能屈才当下测试员了。现在程序员走掉一个，空出来一个位置，那么 $i$ 肯定又能当回程序员了。

如果 $j$ 不来能够使 $i$ 从测试员变成程序员，我们得到了如下三重判断：

• $a_j > b_j$
• $i$ 刚好是第 $n+1$ 个满足 $a_i > b_i$ 的。$j$ 走掉之后 $i$ 变成了第 $n$ 个，所以转职了。

反之亦然。

第二部分：岗位分配与能力值计算

关键变量记录

接下来的事情就很好办了。记录一下第 $n+1$ 个满足 $a_i > b_i$ 的 $i$ 和第 $m+1$ 个满足 $b_i > a_i$ 的 $i$，分别记为 time3 和 time4（胡乱取的变量名），容易发现 time3 和 time4 只会有一个有值。很好理解，如果 time3 和 time4 都有值，那么至少有 $n+1$ 个满足 $a_x > b_x$ 的 $x$ 和 $m+1$ 个满足 $b_y > a_y$ 的 $y$，那么至少有 $n+m+2$ 个面试者，与题目条件“总共有 $n+m+1$ 个面试者”矛盾。

初始能力值计算

接下来就是对答案的处理。首先记录一个 ans 表示如果录取了所有面试者，公司的能力值。其中，对于第 $n+m+1$ 个面试者，如果 $a_i > b_i$，其是测试员；反之则是程序员。这样设表示其被强制转职了。

枚举处理每个面试者

从 $1$ 到 $n+m+1$ 枚举每一个面试者 $i$：

• 如果 $a_i > b_i$，并且满足 time3 有值且 $i < \text{time3}$，说明面试者 time3 的职位改变了，输出：ans - $a_i$ + $a​_{time3}$ - $b_{time3}$,反之，$i$ 一定是一个测试员，输出：ans-$b_i$
• 如果 $b_i > a_i$ 也是同样的道理（对称处理）。
  

#include<bits/stdc++.h>
using namespace std;
long long a[2001000], b[2001000];
int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n + m + 1; i++)
		{
			scanf("%lld", &a[i]);
		}
		for (int i = 1; i <= n + m + 1; i++)
		{
			scanf("%lld", &b[i]);
		}
		int time1 = 0, time2 = 0, time3 = 2e5 + 100, time4 = 2e5 + 100;
		long long ans = 0;
		for (int i = 1; i <= n + m + 1; i++)
		{
			if (a[i] > b[i])
			{
				if (time1 < n)
				{
					time1++;
					ans += a[i];
				}
				else
				{
					ans += b[i];
					if (time1 == n)
					{
						time1++;
					}
				}
			}
			else if (a[i] < b[i])
			{
				if (time2 < m)
				{
					time2++;
					ans += b[i];
				}
				else
				{
					ans += a[i];
					if (time2 == m)
					{
						time2++;
					}
				}
			}
			if (time1 == n + 1 && time3 == 2e5 + 100)
			{
				time3 = i;
			}
			if (time2 == m + 1 && time4 == 2e5 + 100)
			{
				time4 = i;
			}
		}
		//printf("%d %d\n", time3, time4);
		long long ans1;
		for (int i = 1; i <= m + n + 1; i++)
		{
			ans1 = ans;
			if (a[i] > b[i])
			{
				if (i < time3)
				{
					ans1 -= a[i];
					ans1 = ans1 + a[time3] - b[time3];
				}
				else
				{
					ans1 -= b[i];
				}
			}
			if (a[i] < b[i])
			{
				if (i < time4)
				{
					ans1 -= b[i];
					ans1 = ans1 + b[time4] - a[time4];
				}
				else
				{
					ans1 -= a[i];
				}
			}
			printf("%lld ", ans1);
		}
		printf("\n");
	}
	return 0;
}