【题目描述】
给定整数序列 a0,a1,...,aN−1 和 b0,b1,...,bM−1。这里 a 与 b 都是凸的。计算按下式定义的整数序列 c0,c1,...,c(N−1)+(M−1):
ck=i+j=kmin(ai+bj)【输入】
文本
$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$
【输出】
文本
$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$
【输入样例】
文本
4 5
3 1 0 3
5 2 1 1 4
【输出样例】
【数据范围】
- 1≤N,M≤524288
- 0≤ai,bi≤109
- a 是凸的,即对 0≤i<N−2 有 ai+1−ai≤ai+2−ai+1。
- b 是凸的,即对 0≤i<M−2 有 bi+1−bi≤bi+2−bi+1。
【来源】
Library Checker(yosupo06) min_plus_convolution_convex_convex