Min-Max Array Transformation

题意翻译

## 题目描述 给你一个升序数组 $a_1,a_2,...,a_n$。你要通过以下步骤去得到数组 $b_1,b_2,...,b_n$ ： 1. 生成数组 $d$，由$n$个非负整数组成。 2. 通过 $b_i=a_i+d_i$ 计算每一个 $b_i$。 3. 给 $b$ 进行升序排序。 你现在又知道了结果 $b$，你要算出每一个 $d_i$ 可能的最小值和最大值（每个 $d_i$ 的最值可以是由不同的数组 $d$ 满足的）。 ## 输入格式 第一行一个整数 $t (1\le t \le 10^4)$，样例数。 每个样例的第一行一个整数 $n (1 \le n \le 2 * 10^5)$ 。 下一行 $n$ 个整数，$a_1,a_2,...,a_n (1 \le a_1 \le a_2 \le ... \le a_n \le 10^9)$。 下一行 $n$ 个整数，$b_1,b_2,...,b_n (1 \le b_1 \le b_2 \le ... \le b_n \le 10^9)$。 输入数据满足至少有一个满足题意的 $d$。 所有的 $n$ 和不超 $2 * 10^5$。 ## 输出格式 每个样例两行： 第一行 $d_1^{min}, d_2^{min},..., d_n^{min}$。 第二行 $d_1^{max}, d_2^{max},..., d_3^{max}$。 ## 说明/提示 第一个样例中，$d=[5,10,6]$ 满足 $d_1^{min}=5,b=[2+5,3+10,5+6]=[7,13,11]=[7,11,13]$。 第一个样例中，$d=[9,4,8]$ 满足 $d_2^{min}=4,b=[2+9,3+4,5+8]=[11,7,13]=[7,11,13]$。

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ , which is sorted in non-descending order. You decided to perform the following steps to create array $ b_1, b_2, \dots, b_n $ : 1. Create an array $ d $ consisting of $ n $ arbitrary non-negative integers. 2. Set $ b_i = a_i + d_i $ for each $ b_i $ . 3. Sort the array $ b $ in non-descending order. You are given the resulting array $ b $ . For each index $ i $ , calculate what is the minimum and maximum possible value of $ d_i $ you can choose in order to get the given array $ b $ . Note that the minimum (maximum) $ d_i $ -s are independent of each other, i. e. they can be obtained from different possible arrays $ d $ .

输入输出格式

输入格式

The first line contains the single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of arrays $ a $ , $ b $ and $ d $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ; $ a_i \le a_{i+1} $ ) — the array $ a $ in non-descending order. The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le 10^9 $ ; $ b_i \le b_{i+1} $ ) — the array $ b $ in non-descending order. Additional constraints on the input: - there is at least one way to obtain the array $ b $ from the $ a $ by choosing an array $ d $ consisting of non-negative integers; - the sum of $ n $ doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print two lines. In the first line, print $ n $ integers $ d_1^{min}, d_2^{min}, \dots, d_n^{min} $ , where $ d_i^{min} $ is the minimum possible value you can add to $ a_i $ . Secondly, print $ n $ integers $ d_1^{max}, d_2^{max}, \dots, d_n^{max} $ , where $ d_i^{max} $ is the maximum possible value you can add to $ a_i $ . All $ d_i^{min} $ and $ d_i^{max} $ values are independent of each other. In other words, for each $ i $ , $ d_i^{min} $ is just the minimum value among all possible values of $ d_i $ .

输入输出样例

输入样例 #1

4
3
2 3 5
7 11 13
1
1000
5000
4
1 2 3 4
1 2 3 4
4
10 20 30 40
22 33 33 55

输出样例 #1

5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15

说明

In the first test case, in order to get $ d_1^{min} = 5 $ , we can choose, for example, $ d = [5, 10, 6] $ . Then $ b $ $ = $ $ [2+5,3+10,5+6] $ $ = $ $ [7,13,11] $ $ = $ $ [7,11,13] $ . For $ d_2^{min} = 4 $ , we can choose $ d $ $ = $ $ [9, 4, 8] $ . Then $ b $ $ = $ $ [2+9,3+4,5+8] $ $ = $ $ [11,7,13] $ $ = $ $ [7,11,13] $ .

**题目大意：**

给你一个升序数组 $ a_1, a_2, \dots, a_n $。你要通过以下步骤去得到数组 $ b_1, b_2, \dots, b_n $：

1. 生成数组 $ d $，由 $ n $ 个非负整数组成。
2. 通过 $ b_i = a_i + d_i $ 计算每一个 $ b_i $。
3. 给 $ b $ 进行升序排序。

你现在又知道了结果 $ b $，你要算出每一个 $ d_i $ 可能的最小值和最大值（每个 $ d_i $ 的最值可以是由不同的数组 $ d $ 满足的）。

**输入输出数据格式：**

**输入格式：**

第一行一个整数 $ t (1 \le t \le 10^4) $，样例数。

每个样例的第一行一个整数 $ n (1 \le n \le 2 \cdot 10^5) $。

下一行 $ n $ 个整数，$ a_1, a_2, \dots, a_n (1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9) $。

下一行 $ n $ 个整数，$ b_1, b_2, \dots, b_n (1 \le b_1 \le b_2 \le \dots \le b_n \le 10^9) $。

输入数据满足至少有一个满足题意的 $ d $。所有的 $ n $ 和不超 $ 2 \cdot 10^5 $。

**输出格式：**

每个样例两行：

第一行 $ d_1^{min}, d_2^{min}, \dots, d_n^{min} $。

第二行 $ d_1^{max}, d_2^{max}, \dots, d_3^{max} $。**题目大意：** 给你一个升序数组 $ a_1, a_2, \dots, a_n $。你要通过以下步骤去得到数组 $ b_1, b_2, \dots, b_n $： 1. 生成数组 $ d $，由 $ n $ 个非负整数组成。 2. 通过 $ b_i = a_i + d_i $ 计算每一个 $ b_i $。 3. 给 $ b $ 进行升序排序。 你现在又知道了结果 $ b $，你要算出每一个 $ d_i $ 可能的最小值和最大值（每个 $ d_i $ 的最值可以是由不同的数组 $ d $ 满足的）。 **输入输出数据格式：** **输入格式：** 第一行一个整数 $ t (1 \le t \le 10^4) $，样例数。 每个样例的第一行一个整数 $ n (1 \le n \le 2 \cdot 10^5) $。 下一行 $ n $ 个整数，$ a_1, a_2, \dots, a_n (1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9) $。 下一行 $ n $ 个整数，$ b_1, b_2, \dots, b_n (1 \le b_1 \le b_2 \le \dots \le b_n \le 10^9) $。 输入数据满足至少有一个满足题意的 $ d $。所有的 $ n $ 和不超 $ 2 \cdot 10^5 $。 **输出格式：** 每个样例两行： 第一行 $ d_1^{min}, d_2^{min}, \dots, d_n^{min} $。 第二行 $ d_1^{max}, d_2^{max}, \dots, d_3^{max} $。