max+ 或卷积

· · 算法·理论

给定长度为 2^n 的 0-indexed 数组 a,b，求长度为 2^n 的数组 c 满足：

c_i=\max_{j|k=i}a_j+b_k

不难注意到这是一个位运算（或）上的 (\max,+) 卷积。我们考虑分治。将三个序列折半，分别记为 a_0,a_1,b_0,b_1,c_0,c_1。乘法表示对应加，\max 表示对应位取 \max。我们有

c_0=a_0b_0 c_1=\max(a_0b_1,a_1b_0,a_1b_1)=\max(a_0b_1,a_1\max(b_0,b_1))

我们递归下去做就行，复杂度 T(n)=3T\left(\dfrac n2\right)+\Theta(n)=3^{\log_2 n}。

void solve(int * a, int * b, int * c, int * tmp, int n) {
    if (n == 1) return void (*c = max(*c, *a + *b));
    solve(a, b, c, tmp, n >> 1);
    solve(a, b + (n >> 1), c + (n >> 1), tmp, n >> 1);
    rep(i, 0, (n >> 1) - 1) tmp[i] = b[i], b[i] = max(b[i], b[i + (n >> 1)]);
    solve(a + (n >> 1), b, c + (n >> 1), tmp + (n >> 1), n >> 1);
    rep(i, 0, (n >> 1) - 1) b[i] = tmp[i];
}