#P7991. [2021年山东省队集训]超脑星球

    ID: 8004 传统题 1000ms 256MiB 尝试: 3 已通过: 3 难度: 9 上传者: 标签>CF2700省选/NOI-绝对值分段线性化指定流量最小费用流辅助点压缩边残量增广路二叉堆懒删除

[2021年山东省队集训]超脑星球

题目描述

在我们超脑星球上,floyd 90 分钟跑不了 100 的数据范围,可能是因为超脑星球在一个黑洞旁边,导致其时间流速和地球差的很远。

从此时此刻起,忘记地球吧。我们脚下的这片土地的名字,叫做超脑星球。你们面前必须只能是星辰与大海。接下来就让我们一起来看看,在超脑星球上,到底有什么有趣迷人又刺激的事情会发生呢:

给定一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n,还有 mm 个整数 b1,b2,…,bmb_1,b_2,\ldots,b_m。

你要从这 mm 个整数中选出正好 ii 个,并将他们插入到序列 aa 中,注意不能插到头部或尾部。

同时需要满足,每对 aja_j 和 aj+1a_{j+1} 之间,至多只插入了一个 bb 序列中的元素。

要求最大化新生成的序列中,相邻元素差的绝对值之和。

对于所有 ii 满足 1≤i≤m1\leq i\leq m,均需输出答案。

输入格式

第一行两个整数 nn 和 mm 分别表示序列 aa 和序列 bb 的长度。

第二行 nn 个整数,表示序列 aa 的元素。

第三行 mm 个整数,表示序列 bb 的元素。

输出格式

输出一行 mm 个整数,第 ii 个表示恰好选取 ii 个时的答案。

样例 #1

样例输入 #1

10 8
2 25 29 2 28 20 24 8 30 27
13 21 17 18 14 30 9 23

样例输出 #1

169 193 205 217 223 223 223 223

提示

对于 10%10\% 的数据,n≤50n\leq 50;

对于 30%30\% 的数据,n≤600n\leq 600;

对于 40%40\% 的数据,n≤1000n\leq 1000;

对于 60%60\% 的数据,n≤5000n\leq 5000;

对于 100%100\% 的数据,1≤m<n≤105,1≤ai,bi≤1081\leq m<n\leq 10^5,1\leq a_i,b_i\leq 10^8。