【思维构造】Neutral Tonality—CF1894D

Neutral Tonality—CF1894D

翻译

给定一个由$n$个整数组成的数组$a$，以及一个由$m$个整数组成的数组$b$。

$\text{LIS}(c)$表示数组$c$的最长递增子序列的长度。例如，$\text{LIS}([2,\underline{1},1,\underline{3}])$ = $2$，$\text{LIS}([\underline{1},\underline{7},\underline{9}])$ = $3$，$\text{LIS}([3,\underline{1},\underline{2},\underline{4}])$ = $3$。

你需要将数字$b_1,b_2,\dots ,b_m$插入到数组$a$中的任意位置，任意顺序。令结果数组为$c_1,c_2,\dots ,c_{n+m}$。你需要选择插入位置以最小化$\text{LIS}(c)$。

也就是说，你需要找到一个数组$c_1,c_2,\dots ,c_{n+m}$，同时满足以下条件：

• 数组$a_1,a_2,\dots ,a_n$是数组$c_1,c_2,\dots ,c_{n+m}$的子序列。
• 数组$c_1,c_2,\dots ,c_{n+m}$由数字$a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_m$组成，可能重新排列。
• $\text{LIS}(c)$的值是所有合适数组$c$中最小可能的值。

输入

每个测试包含多个测试用例。第一行包含一个整数$t$ $(1\le t\le 10^4)$，表示测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数$n,m$ $(1\le n\le 2\cdot 10^5,1\le m\le 2\cdot 10^5)$，表示数组$a$和数组$b$的长度。

每个测试用例的第二行包含$n$个整数$a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^9)$，表示数组$a$的元素。

每个测试用例的第三行包含$m$个整数$b_1,b_2,\dots ,b_m$ $(1\le b_i\le 10^9)$，表示数组$b$的元素。

保证所有测试用例中$n$的总和不超过$2\cdot 10^5$，$m$的总和不超过$2\cdot 10^5$。

输出

对于每个测试用例，输出$n+m$个数字，即插入后获得的最终数组$c_1,c_2,\dots ,c_{n+m}$的元素，使得$\text{LIS}(c)$的值最小化。如果有多个答案，可以输出其中任意一个。

注意

第一个测试用例中，$\text{LIS}(a)=\text{LIS}([6,4])=1$。我们可以在$6$和$4$之间插入数字$5$，然后$\text{LIS}(c)=\text{LIS}([6,5,4])=1$。

第二个测试用例中，$\text{LIS}([\underline{1},7,\underline{2},\underline{4},\underline{5}])$ = $4$。插入后，$c=[1,1,7,7,2,2,4,4,5,5]$。很容易看出$\text{LIS}(c)=4$。可以证明无法使$\text{LIS}(c)$小于$4$。

思路

为了使插入的 $b$ 数组对 $\text{LIS}$ 的贡献最小，我们很容易想到插入的 $b$ 数组中各个元素的大小应该是降序的。

这种情况下，对于 $a$ 中的每个上升子序列，$b$ 中最多只会有一个元素对其做出了贡献（假设有两个做出了贡献，那么这两个构成降序序列，破坏了整体的升序性质）。

那么就不难得到：$\text{LIS}(a)\le \text{LIS}(c)\le \text{LIS}(a)+1$。

现在我们考虑能不能找到一种插入方法，使得 $\text{LIS}(a)=\text{LIS}(c)$ 恒成立。

答案是有的。那就是把 $c$ 数组分成若干组，使得每一组中只有最多只有一个元素出现在某个上升子序列中。上边这句话有没有一种熟悉的感觉？是不是和上边第二段的让 $b$ 数组降序的想法很相似？所以这里我们让 $c$ 中的每一组内部都成降序分布。

具体来说，我们降序排序好 $b$ 后，顺序遍历 $a$ 数组，把当前 $b$ 中剩余的满足 $b_j\ge a_i$ 的元素加到 $a_i$ 左边（$a_{i-1}$ 右边）。配合代码更好理解。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n, m;
int a[N], b[N];

void solve(int Case) {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= m; i ++) cin >> b[i];
	
	sort(b + 1, b + m + 1, greater<int>());
	
	int j = 1;
	for (int i = 1; i <= n; i ++) {
		while (j <= m && b[j] >= a[i]) {
			cout << b[j ++] << " ";
		}
		cout << a[i] << " ";
	}
	while (j <= m) {;
		cout << b[j ++] << " ";
	}
	cout << "\n";
}

signed main() {
	cin.tie(0)->ios::sync_with_stdio(false);
	int T = 1;
	cin >> T; cin.get();
	int Case = 0;
	while (++ Case <= T) solve(Case);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40