题目 30022

Min-Plus 卷积(凸 × 凸)

查看题解 ↗GitHub ↗如何评测
题号
30022
时间限制
10000 ms
内存限制
1024 MB
标签
数学
来源
Library Checker (yosupo06) - min_plus_convolution_convex_convex

【题目描述】

给定整数序列 a0,a1,...,aN−1a_0, a_1, ..., a_{N - 1} 和 b0,b1,...,bM−1b_0, b_1, ..., b_{M - 1}。这里 aa 与 bb 都是凸的。计算按下式定义的整数序列 c0,c1,...,c(N−1)+(M−1)c_0, c_1, ..., c_{(N - 1) + (M - 1)}:

ck=min⁡i+j=k(ai+bj)c_k = \min_{i+j=k} (a_i+b_j)

【输入】

文本
$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

【输出样例】

文本
8 5 3 2 1 1 4 7

【数据范围】

  • 1≤N,M≤5242881 \leq N, M \leq 524288
  • 0≤ai,bi≤1090 \leq a_i, b_i \leq 10^9
  • aa 是凸的,即对 0≤i<N−20 \leq i < N - 2 有 ai+1−ai≤ai+2−ai+1a_{i+1}-a_i \leq a_{i+2}-a_{i+1}。
  • bb 是凸的,即对 0≤i<M−20 \leq i < M - 2 有 bi+1−bi≤bi+2−bi+1b_{i+1}-b_i \leq b_{i+2}-b_{i+1}。

【来源】

Library Checker(yosupo06) min_plus_convolution_convex_convex

数据下载

题目 30022 的公开数据

正在读取文件列表…

常用命令

题目 30022 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。