分数: 900 点
问题陈述
定义 成本 树的 一个序列的 X as(最大值 X 减去最小值 X).
给定了序列 A = (A_1, \ldots, A_N) 和 B = (B_1, \ldots, B_N) 长度 N。解决以下问题 k = 1, 2, \ldots, N.
- 找到序列的最小可能成本 C = (C_1, \ldots, C_k) 谁 i- 第一个元素 C_i is A_i or B_i.
约束
- 所有输入数字均为整数。
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N B_1 \ldots B_N
输出
打印 N 行。
的 i第行 (1 \leq i \leq N) 应包含序列的最小可能成本 C 为 k = i.
示例输入 1
3 8 11 10 7 6 1
示例输出 1
0 1 3
对于 k=1,如果我们选择 C = (8),成本 C is 0,这是最小值。
对于 k=2,如果我们选择 C = (7,6),成本 C is 1,这是最小值。
对于 k=3,如果我们选择 C = (8,11,10),成本 C is 3,这是最小值。
示例输入 2
10 43 35 36 58 25 7 61 4 96 3 55 29 88 15 99 49 67 57 92 49
示例输出 2
0 8 8 23 28 33 36 36 64 64