B. 水母与满天星 详细题解

问题重述

给定两个长度为$n$的排列$p$和$q$，元素均为$[0, n-1]$的整数。需要计算数组$r$，其中：

$$r_i = \max_{j=0}^{i} \left( 2^{p_j} + 2^{q_{i-j}} \right) \quad \text{对于 } 0 \le i \le n-1 $$

输出所有$r_i$对$998244353$取模的结果。

---

核心难点分析

1. 如何快速比较$2^a + 2^b$和$2^c + 2^d$

直接计算幂次并比较数值可能超出整数范围，但注意到$2^k$在二进制表示中只有第$k$位为$1$。因此：

• 若$a > c$且$a > d$，则$2^a + 2^b > 2^c + 2^d$
• 比较两个形如$2^a + 2^b$的数，等价于比较它们的二进制最高位：
  • 首先比较最大值$\max(a, b)$与$\max(c, d)$
  • 若最大值相等，再比较次大值

2. 排列性质的作用

题目强调$p$和$q$是排列，这意味着：

• 每个值$0$到$n-1$在$p$中恰好出现一次
• 每个值$0$到$n-1$在$q$中恰好出现一次

这个性质确保了：

• 当我们遍历索引时，当前看到的$p$和$q$的最大值会单调递增
• 每个最大值只会在一个位置出现，便于跟踪

---

算法核心思想

前缀最大值跟踪

定义：

• $i$ = 当前已遍历的$p$中最大值所在位置
• $j$ = 当前已遍历的$q$中最大值所在位置

对于固定的$k$，考虑所有$j \in [0, k]$：

• 表达式为$2^{p_j} + 2^{q_{k-j}}$

关键引理

对于任意$k$，最大值一定出现在以下两种情况之一：

1. 固定$p$取当前最大值：取$j = i$，得到$2^{p_i} + 2^{q_{k-i}}$
2. 固定$q$取当前最大值：取$j = k-j$，得到$2^{p_{k-j}} + 2^{q_j}$

证明：假设最大值由$p_a$和$q_b$贡献，且$a + b = k$。若$p_a$不是当前$p$的最大值，则存在$a' \le k$使得$p_{a'} > p_a$。那么取$j = a'$，得到$2^{p_{a'}} + 2^{q_{k-a'}}$一定大于等于原值（第一项更大，第二项可能不同）。同理可证$q$部分。因此，最大值必然可以由至少一个部分取当前最大值达到。

---

算法流程

设：

• $i$ = 当前$p$中最大值的位置
• $j$ = 当前$q$中最大值的位置

遍历$k$从$0$到$n-1$：

步骤 1：更新最大值位置

• 若$p[k] > p[i]$，则$i = k$
• 若$q[k] > q[j]$，则$j = k$

步骤 2：根据$p[i]$和$q[j]$的关系计算$r_k$

情况 1：$p[i] > q[j]$ 此时$p[i]$是当前所有数中的最大值，因此最大值必定由$p[i]$贡献：

$$r_k = 2^{p[i]} + 2^{q_{k-i}}$$

情况 2：$p[i] < q[j]$ 此时$q[j]$是当前所有数中的最大值，因此最大值必定由$q[j]$贡献：

$$r_k = 2^{q[j]} + 2^{p_{k-j}}$$

情况 3：$p[i] = q[j]$ 两个最大值相等，需要比较次大项：

$$r_k = 2^{p[i]} + \max\left(2^{q_{k-i}}, 2^{p_{k-j}}\right) $$

---

标程解析

const int N = 1e5 + 5, Mod = 998244353;
int n = 0, s[N] = {}, p[N] = {}, q[N] = {}, r[N] = {};

int main(){
    // 预计算 $2^i \bmod MOD$
    s[0] = 1; 
    for(int i = 1 ; i < N ; i ++) 
        s[i] = s[i - 1] * 2 % Mod;
    
    scanf("%d", &T);
    while(T --) solve();
    return 0;
}

预计算数组s：s[i]存储$2^i \bmod 998244353$，避免重复计算。

inline void solve(){
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i ++) scanf("%d", &p[i]);
    for(int i = 0 ; i < n ; i ++) scanf("%d", &q[i]);
    
    for(int i = 0, j = 0, k = 0 ; k < n ; k ++){
        // 更新当前最大值的位置
        if(p[k] > p[i]) i = k; 
        if(q[k] > q[j]) j = k;
        
        // 根据情况计算 $r_k$
        if(p[i] != q[j]){
            if(p[i] > q[j]) 
                printf("%d ", (s[p[i]] + s[q[k - i]]) % Mod);
            else 
                printf("%d ", (s[q[j]] + s[p[k - j]]) % Mod);
        }
        else 
            printf("%d ", (s[p[i]] + s[max(q[k - i], p[k - j])]) % Mod);
    }
    printf("\n");
}

关键点：

• i和j始终指向当前已遍历元素中$p$和$q$的最大值位置
• 对于每个$k$，只需计算常数个候选值，无需遍历所有$j$
• 利用排列性质确保最大值单调递增，无需回退

---

正确性证明

定理：对于任意$k$，上述算法计算的$r_k$等于$\max_{j=0}^{k} (2^{p_j} + 2^{q_{k-j}})$。

证明：由引理可知，最大值必然可以由以下两种形式之一达到：

1. 取$j = i$，其中$i$是$p$当前最大值的下标
2. 取$j = k-j$，其中$j$是$q$当前最大值的下标

算法考虑了这两种情况：

• 当$p[i] \neq q[j]$时，较大的那个一定是全局最大值，因此只需考虑对应的一种情况
• 当$p[i] = q[j]$时，两种情况的第一个加数相等，只需比较第二个加数取最大值

因此算法正确。

---

时间复杂度分析

• 预处理$s$数组：$O(N)$，其中$N = 10^5$
• 每个测试用例：$O(n)$
• 总复杂度：$O(\sum n + N) \le O(2 \times 10^5)$，完全可行

---

示例验证

以第一个测试用例为例：

• $p = [0, 2, 1]$，$q = [1, 2, 0]$

遍历过程：

$k = 0$：

• 初始：$i = 0, j = 0$
• 更新后：$i = 0, j = 0$
• $p[i] = 0$，$q[j] = 1$，$p[i] < q[j]$
• $r_0 = 2^{q[0]} + 2^{p[0]} = 2^1 + 2^0 = 2 + 1 = 3$

$k = 1$：

• 更新：$p[1] = 2 > p[0] = 0$，$i = 1$；$q[1] = 2 > q[0] = 1$，$j = 1$
• $p[i] = 2$，$q[j] = 2$，相等
• $r_1 = 2^{p[1]} + \max(2^{q[1-1]}, 2^{p[1-1]}) = 2^2 + \max(2^{q[0]}, 2^{p[0]}) = 4 + \max(2, 1) = 6$

$k = 2$：

• $i = 1, j = 1$保持不变
• $p[i] = 2$，$q[j] = 2$，相等
• $r_2 = 4 + \max(2^{q[1]}, 2^{p[1]}) = 4 + \max(4, 4) = 8$

输出：$3\ 6\ 8$，与题目示例一致。