题目 E. 狭窄通道 详细题解

问题重述

有一个 $2$ 行 $N$ 列的网格，每个格子 $(r,c)$ 有一个正整数权值 $P_{r,c}$。
每天，每一列有 $50\%$ 的概率被雾覆盖（即该列的两个格子都不部署士兵）。未被雾覆盖的列形成若干个连通区域（连续的不被雾覆盖的列区间）。
对于一个连通区域 $[u,v]$，定义

$$m_1 = \max_{c=u}^v P_{1,c},\quad m_2 = \max_{c=u}^v P_{2,c} $$

若 $m_1 = m_2$，则该区域强度为 $0$；否则强度为 $\min(m_1,m_2)$。
总强度为所有连通区域的强度之和。求期望总强度，输出模 $M=998244353$ 下的值（即 $x \cdot y^{-1} \bmod M$）。

---

解题思路

采用贡献法：每个格子 $(r,c)$ 的权值 $P_{r,c}$ 对期望总强度的贡献为

$$P_{r,c} \times \text{prob}(r,c)$$

其中 $\text{prob}(r,c)$ 是“存在一个连通区域，使得该区域的强度恰好取到 $P_{r,c}$（即 $P_{r,c}$ 是该区域所在行的最大值，且另一行的最大值大于 $P_{r,c}$）”的概率。
因为期望具有线性性，总期望 = $\sum_{r,c} P_{r,c} \cdot \text{prob}(r,c)$。

---

如何计算 $\text{prob}(r,c)$

考虑一个固定的格子 $(r,c)$，设另一行为 $r'$（$r' = 3-r$）。
我们要统计所有可能的连通区域 $[u,v]$ 满足：

1. $u \le c \le v$。
2. $P_{r,c}$ 是第 $r$ 行在区间 $[u,v]$ 上的最大值（即 $P_{r,c} \ge \max_{t\in[u,v]} P_{r,t}$，且由于我们处理的是严格最大情形，需处理相等情况）。
3. 第 $r'$ 行在区间 $[u,v]$ 上的最大值 大于 $P_{r,c}$。

为了高效计算，我们按权值从小到大扫描（sweep）。维护一个数据结构（如并查集或平衡树），记录当前已经激活的格子（即已经被扫描过的、权值较小的格子）。
当处理到权值为 $w$ 的格子时，所有权值小于 $w$ 的格子已经激活，权值等于 $w$ 的格子需要小心处理顺序（通常按列号处理以避免重复计数）。

对于当前格子 $(r,c)$，定义：

• 在其所在行 $r$ 中，向左向右扩展到连续激活格子的最大区间 $[L_1, R_1]$，其中 $L_1 \le c \le R_1$，且区间内所有格子都已激活。
• 在另一行 $r'$ 中，找到最靠近 $c$ 的、权值 大于 $P_{r,c}$ 的列。设：
  • $p_{\text{left}}$ 为 $c$ 左边第一个满足 $P_{r',p} > P_{r,c}$ 的列（若不存在则 $p_{\text{left}} = 0$）。
  • $p_{\text{right}}$ 为 $c$ 右边第一个满足 $P_{r',p} > P_{r,c}$ 的列（若不存在则 $p_{\text{right}} = N+1$）。

则可行的连通区域 $[u,v]$ 必须满足：

• $u$ 在 $[L_1, \min(c, p_{\text{left}}+1)]$ 中？根据题解，定义：$$\text{left}_2 = \max(L_1,\ p_{\text{left}}+1)$$ $$\text{right}_2 = \min(R_1,\ p_{\text{right}}-1)$$ 并且 $u$ 与 $v$ 需满足：
  • 情况 A：$L_1 \le u < \text{left}_2$ 且 $c \le v \le R_1$。
  • 情况 B：$L_1 \le u \le c$ 且 $\text{right}_2 < v \le R_1$。 注意这两个情况可能有重叠（当 $u < \text{left}_2$ 且 $v > \text{right}_2$ 时），需减去一次重复计数。

对于每个这样的 $(u,v)$，它作为一个连通区域出现的概率是：

• 列 $u-1$ 和 $v+1$ 必须有雾（否则区域会更大，不会以 $[u,v]$ 为最大连续段）。
• 列 $1$ 到 $u-2$ 以及 $v+2$ 到 $N$ 可以任意（有雾或无雾，共 $2^{(u-2)+(N-v-1)}$ 种）。
• 所有列被雾覆盖的情况总数为 $2^N$，且每列独立等概率。

因此，概率为：

$$f(u,v) = \frac{2^{(u-2)+(N-v-1)}}{2^N} = 2^{-(v-u+3)} \quad \text{若 } u>1,\ v<N $$

边界情况需特殊处理（当 $u=1$ 时没有左边的雾限制，当 $v=N$ 时没有右边的雾限制）。
更统一地，设 $A = u-1$（左边必须雾的列数），$B = N-v$（右边必须雾的列数），则

$$f(u,v) = \frac{2^{(u-2)+(N-v-1)}}{2^N} = 2^{-(v-u+1)-2} = 2^{-(v-u+3)} $$

当 $u=1$ 时，$u-2$ 为负数，实际上左边没有限制，应视为 $2^{0}$；同理 $v=N$ 时右边无限制。
其实更简单的理解：连通区域 $[u,v]$ 出现的概率 = $\frac{1}{2^{v-u+2}}$？
推导：必须保证 $u-1$ 和 $v+1$ 有雾（如果存在），而 $u..v$ 内无雾，其余列任意。所以概率 = $2^{-(v-u+2)}$。
因为 $u..v$ 共 $len=v-u+1$ 列，这些列必须无雾（概率 $2^{-len}$），且左右边界两列（若存在）必须有雾（额外乘 $2^{-2}$），共 $2^{-(len+2)}$。但若 $u=1$ 则左边无列，概率乘 $2^{-(len+1)}$；若 $v=N$ 则右边无列，概率乘 $2^{-(len+1)}$；若 $u=1$ 且 $v=N$ 则概率 $2^{-len}$。
而题解中的 $f(u,v)$ 表达式实际上是将这些情况统一为：

$$f(u,v) = \frac{1}{2^{v-u+2}} \times \text{修正项？}$$

为了编程方便，我们采用另一种形式：所有可能方案总数为 $2^N$，对于固定的 $[u,v]$，其发生的方式数为 $2^{u-2} \cdot 2^{N-v-1}$（当 $u>1$ 且 $v<N$），分别处理边界。

在实际算法中，我们不是枚举所有 $(u,v)$，而是利用独立计算左右两侧的贡献和。
因为概率可以拆分为左右独立因子：

$$f(u,v) = g_{\text{left}}(u) \cdot h_{\text{right}}(v) $$

其中 $g_{\text{left}}(u)$ 只依赖于 $u$，$h_{\text{right}}(v)$ 只依赖于 $v$，且乘积形式。
具体地，定义：

• 对于左端点 $u$，其左因子为 $2^{-(u-1)}$（当 $u>1$，否则 $1$）。实际上，若 $u>1$，则列 $u-1$ 必须有雾，而 $1..u-2$ 任意，所以左因子为 $2^{-1} \cdot 2^{u-2} = 2^{u-3}$？注意概率分母有 $2^N$，所以需整体归一化。我们改用另一种方式：
  设 $L(u) = 2^{u-2}$（当 $u>1$，否则 $1$），$R(v) = 2^{N-v-1}$（当 $v<N$，否则 $1$），则$$\text{概率} = \frac{L(u) \cdot R(v)}{2^N}$$ 其中 $L(u)$ 是 $[1,u-2]$ 列任意的方案数，$R(v)$ 是 $[v+2,N]$ 列任意的方案数，再乘上 $u-1$ 和 $v+1$ 必须雾（各 1 种），所以总方案数 = $L(u) \cdot R(v)$。分母 $2^N$。
  因此，所有 $[u,v]$ 对概率的贡献可以写成：$$\text{prob}(r,c) = \sum_{u,v \text{ 满足条件}} \frac{L(u) R(v)}{2^N} $$由于 $u,v$ 的约束是独立的（$u$ 属于某个区间，$v$ 属于某个区间，且 $u \le c \le v$），我们可以分别计算：$$\text{prob}(r,c) = \frac{1}{2^N} \left( \sum_{u \in U} L(u) \right) \cdot \left( \sum_{v \in V} R(v) \right) $$其中 $U$ 是满足 $L_1 \le u \le \min(c, \text{left}_2-1)$ 的 $u$ 集合，$V$ 是满足 $\max(c, \text{right}_2+1) \le v \le R_1$ 的 $v$ 集合。实际上还有情况 B 产生另一组 $u,v$，且两者可能重叠，需用容斥。
  详细公式见题解原文：贡献分为左右两部分，可以分别计算前缀和、后缀和，然后相乘得到总方案数，再除以 $2^N$ 即为概率。

---

算法步骤

1. 预处理
   将 $2N$ 个格子按权值 $P_{r,c}$ 升序排序。权值相同的格子需特殊处理：通常按列号顺序处理，保证在计算时，已激活的格子权值小于当前权值，相等但列号更小的视为未激活，以避免重复计数。我们可以规定：当权值相等时，只有列号更小的格子才被认为是“激活”，从而保证当前格子是所在行区间内的严格最大值。

2. 数据结构维护
   使用并查集或平衡树（例如 C++ 的 set）来维护每行中已经激活的格子所形成的连续段。
   对于每行，维护一个 set 存储当前激活的列号。当激活一个格子 $(r,c)$ 时，将其插入集合，并合并相邻的列形成新的连续段。
   同时需要快速查询给定 $c$ 所在的连续段的左右端点 $L_1, R_1$（即包含 $c$ 的最大连续激活区间）。这可以用 set 的 lower_bound 或并查集实现。

3. 对于每个格子 $(r,c)$ 计算贡献

   • 获取当前行 $r$ 的激活区间 $[L_1, R_1]$。
   • 在另一行 $r'$ 中，找到左边第一个权值 $> P_{r,c}$ 的列 $p_{\text{left}}$，右边第一个 $> P_{r,c}$ 的列 $p_{\text{right}}$。因为我们已经按权值升序扫描，另一行中所有权值小于等于当前权值的格子都是激活的，但我们需要的是严格大于，所以这些列应该不在当前激活集合中。我们可以维护另一行所有格子的权值，通过预处理权值排序后二分查找位置。或者直接在另一行的已激活集合中，利用 set 存储列号，但需要快速找到两边第一个未激活且权值大于当前值的格子？然而未激活的不一定权值大。更简单的方法是：预处理每一行每个位置左边第一个权值大于给定值的列，这可以用单调栈预处理所有格子，但这里是在扫描过程中动态变化，因为“大于当前权值”的集合随着扫描而扩大（当前权值逐渐增大）。实际上，由于我们按权值递增处理，当前权值 $w$ 的所有格子之前，权值大于 $w$ 的格子都还没有被激活，因此这些格子的列就是那些尚未被加入激活集合的列。所以我们可以直接利用另一行中 未被激活的列，并从中找出最靠近 $c$ 的左右两边各一个。
     如何快速找到？可以维护另一行的一个 set 存储未激活的列（初始所有列都在）。当激活一个格子时，从该 set 中删除该列。那么 $p_{\text{left}}$ 就是 set 中小于 $c$ 的最大列，$p_{\text{right}}$ 是大于 $c$ 的最小列。这可以用 set 的 lower_bound 实现 $O(\log N)$。
   • 计算 $\text{left}_2 = \max(L_1, p_{\text{left}}+1)$，$\text{right}_2 = \min(R_1, p_{\text{right}}-1)$。
   • 计算情况 A 的 $u$ 范围：$[L_1,\ \text{left}_2-1]$（若 $L_1 \le \text{left}_2-1$）。 $v$ 范围：$[c,\ R_1]$。
   • 情况 B 的 $u$ 范围：$[L_1,\ c]$，$v$ 范围：$[\text{right}_2+1,\ R_1]$（若 $\text{right}_2+1 \le R_1$）。
   • 若两种情况有重叠（即 $u < \text{left}_2$ 且 $v > \text{right}_2$），则需减去重复部分的贡献。该重叠区域对应 $u \in [L_1, \text{left}_2-1]$，$v \in [\text{right}_2+1, R_1]$。
   • 对于每个区间，贡献是：$$\sum_{u \in U} L(u) \cdot \sum_{v \in V} R(v)$$ 其中 $L(u) = 2^{u-2}$（若 $u>1$，否则 $1$），$R(v) = 2^{N-v-1}$（若 $v<N$，否则 $1$）。这些前缀和可以预处理，使得区间和 $O(1)$ 计算：
     • 预处理数组 preL[i] = sum_{u=1}^{i} L(u) 和 sufR[i] = sum_{v=i}^{N} R(v)。 则 $\sum_{u=a}^{b} L(u) = \text{preL}[b] - \text{preL}[a-1]$，$\sum_{v=c}^{d} R(v) = \text{sufR}[c] - \text{sufR}[d+1]$（注意边界）。
   • 将上述三个部分（A、B、重叠）的乘积求和，得到总方案数 ways。
   • 概率 $\text{prob} = \frac{\text{ways}}{2^N}$。由于最终答案要输出模 $M$ 下的 $P_{r,c} \cdot \text{prob}$，我们可以计算：$$\text{contribution} = P_{r,c} \cdot \text{ways} \cdot \text{inv}(2^N) \pmod{M} $$其中 $\text{inv}(2^N)$ 是 $2^N$ 模 $M$ 的逆元。
   • 累加贡献到答案。

4. 处理重复计数
   当权值相等时，需要保证只有其中一个格子被视为严格最大。题解中建议按列号顺序处理：对于相同权值的格子，在扫描时，先处理列号较小的，且对于列号较大的，其“当前激活集合”中不包含列号较小但权值相等的格子（因为这些格子虽已扫描但未加入激活，或者加入激活但设定严格大于）。通常做法是：在扫描过程中，只有当当前格子的权值严格大于已激活格子的权值时，才将其加入激活集合。对于相等权值，我们可以在同一权值内部按列号从大到小（或从小到大）顺序处理，并保证在计算贡献时，同一行的其他相等权值格子尚未被激活，从而形成“严格大于”的条件。另一种简单方法：排序时，将权值作为第一关键字，列号作为第二关键字（例如升序），然后在处理过程中，对于权值相同的格子，它们不会互相激活，因此对于每个格子，另一行中同权值的格子可能已经激活（如果列号较小且已被处理）？需要仔细设计。题解中说明：可以通过“先处理较小的列号，然后添加条件：当前格子权值严格大于活动格子中列号更大的那些”来避免重复。通常的做法是：在排序时按权值升序，权值相同时按列号降序（这样先处理大列号，使得小列号在后面时，大列号已经被激活，且权值相等，但此时小列号尚未激活，因此大列号不会把小列号当作“激活”来影响区间，因为我们对另一行找的是权值大于当前格子的列，相等的不算，所以安全）。更通用的方法是使用“权值严格大于”的比较，因此相等权值不会互相干扰，只要保证我们在当前格子的扫描阶段，另一行中权值等于当前值的格子还未被加入激活集合即可。我们可以先处理所有权值小于当前值的格子，然后对于相同权值的格子，单独处理（不将它们互相激活），最后再统一激活。实现时，将格子分组按权值，对每组内，先计算该组所有格子的贡献（此时激活集合中只有权值更小的格子），然后才将该组格子加入激活集合。

5. 最终答案
   输出 $\sum_{r,c} \left( P_{r,c} \cdot \text{ways}_{r,c} \cdot \text{inv}(2^N) \right) \bmod M$。

---

复杂度分析

• 排序 $O(N \log N)$。
• 使用 set 维护每行的激活段和未激活列，每次操作 $O(\log N)$。
• 每个格子计算贡献 $O(\log N)$（查询左右边界、前缀和计算 $O(1)$）。
• 总时间复杂度 $O(N \log N)$，空间 $O(N)$。

---

模运算细节

• 模数 $M = 998244353$。
• 需要预计算 $2^k \bmod M$ 以及 $2^{-k} \bmod M$。由于 $2^N$ 可能很大，用快速幂求逆元。
• 预处理 preL[i] 和 sufR[i] 时，直接使用模 $M$ 下的值，但注意 $L(u)$ 和 $R(v)$ 可能很大（$2^{u-2}$），需取模。因为最终要除以 $2^N$，我们可以将分母处理为乘上逆元。

---

参考代码框架

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAXN = 100005;

int N;
int P[2][MAXN];
ll pow2[MAXN], inv_pow2[MAXN];
ll preL[MAXN], sufR[MAXN];

ll modpow(ll a, ll e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

void precompute() {
    pow2[0] = 1;
    for (int i = 1; i <= N+5; i++) pow2[i] = pow2[i-1] * 2 % MOD;
    ll inv2 = modpow(2, MOD-2);
    inv_pow2[0] = 1;
    for (int i = 1; i <= N+5; i++) inv_pow2[i] = inv_pow2[i-1] * inv2 % MOD;
    // L(u) = 2^{u-2} for u>1, else 1
    for (int u = 1; u <= N; u++) {
        ll val = (u == 1) ? 1 : pow2[u-2];
        preL[u] = (preL[u-1] + val) % MOD;
    }
    // R(v) = 2^{N-v-1} for v<N, else 1
    for (int v = N; v >= 1; v--) {
        ll val = (v == N) ? 1 : pow2[N-v-1];
        sufR[v] = (sufR[v+1] + val) % MOD;
    }
}

struct Cell {
    int r, c, val;
    bool operator<(const Cell& o) const {
        if (val != o.val) return val < o.val;
        // 按列号排序，保证同权值处理顺序
        return c < o.c; // 或者降序，需配合激活策略
    }
};

set<int> active[2];   // 每行已激活的列
set<int> inactive[2]; // 每行未激活的列（用于找大于当前值的最近列）

void activate(int r, int c) {
    active[r].insert(c);
    inactive[r].erase(c);
}

// 获取包含列c的最大连续激活区间 [L,R]
pair<int,int> get_interval(int r, int c) {
    auto it = active[r].find(c);
    int L = c, R = c;
    if (it != active[r].begin()) {
        auto pit = prev(it);
        if (*pit == c-1) L = *active[r].begin(); // 需找到最左
        // 更简单：向前遍历直到不连续，但 O(长度) 不行。
        // 实际可用并查集，或维护每个激活段的端点。这里为了简洁，使用 set 连续段合并。
        // 推荐使用 map 存储每个连续段的左右端点，但实现较复杂。
    }
    // 由于我们只需要在 get_interval 时知道左右边界，可以在激活时维护并查集。
    // 另一种方法：用并查集（DSU）维护每行的连续段，每次激活时合并左右。
    // 这里不展开具体实现，假设已有函数 get_interval(r,c) 返回 L,R。
    return {L, R};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < 2; i++)
        for (int j = 1; j <= N; j++)
            cin >> P[i][j];
    precompute();

    vector<Cell> cells;
    for (int r = 0; r < 2; r++)
        for (int c = 1; c <= N; c++)
            cells.push_back({r, c, P[r][c]});
    sort(cells.begin(), cells.end());

    // 初始化 inactive 集合
    for (int r = 0; r < 2; r++) {
        for (int c = 1; c <= N; c++) inactive[r].insert(c);
    }

    ll inv_2N = modpow(pow2[N], MOD-2);
    ll ans = 0;

    // 按权值分组处理
    int i = 0;
    while (i < (int)cells.size()) {
        int cur_val = cells[i].val;
        vector<Cell> group;
        while (i < (int)cells.size() && cells[i].val == cur_val) {
            group.push_back(cells[i]);
            i++;
        }
        // 先计算组内所有格子的贡献（此时激活集合中只有权值更小的格子）
        for (auto& cell : group) {
            int r = cell.r, c = cell.c;
            int r1 = r, r2 = 1 - r; // 另一行
            // 获取当前行激活区间
            auto [L1, R1] = get_interval(r1, c); // 需要实现 get_interval
            // 在另一行的未激活集合中找左右第一个大于当前值的列
            auto it = inactive[r2].lower_bound(c);
            int p_right = (it != inactive[r2].end()) ? *it : N+1;
            int p_left = -1;
            if (it != inactive[r2].begin()) {
                p_left = *prev(it);
            }
            int left2 = max(L1, p_left+1);
            int right2 = min(R1, p_right-1);
            // 计算方案数
            ll ways = 0;
            // 情况 A: u in [L1, left2-1], v in [c, R1]
            if (L1 <= left2-1) {
                ll sumU = (preL[left2-1] - preL[L1-1] + MOD) % MOD;
                ll sumV = (sufR[c] - sufR[R1+1] + MOD) % MOD;
                ways = (ways + sumU * sumV) % MOD;
            }
            // 情况 B: u in [L1, c], v in [right2+1, R1]
            if (right2+1 <= R1) {
                ll sumU = (preL[c] - preL[L1-1] + MOD) % MOD;
                ll sumV = (sufR[right2+1] - sufR[R1+1] + MOD) % MOD;
                ways = (ways + sumU * sumV) % MOD;
            }
            // 重叠部分 (u in [L1, left2-1], v in [right2+1, R1]) 被加了两次，减去一次
            if (L1 <= left2-1 && right2+1 <= R1) {
                ll sumU = (preL[left2-1] - preL[L1-1] + MOD) % MOD;
                ll sumV = (sufR[right2+1] - sufR[R1+1] + MOD) % MOD;
                ways = (ways - sumU * sumV % MOD + MOD) % MOD;
            }
            ll prob = ways * inv_2N % MOD;
            ans = (ans + (ll)P[r][c] * prob) % MOD;
        }
        // 将组内所有格子激活
        for (auto& cell : group) {
            activate(cell.r, cell.c);
        }
    }
    cout << ans << '\n';
    return 0;
}

注意：上述代码中的 get_interval 函数需要高效实现。通常可以用并查集维护每行连续段的左右端点：当激活一个列 $c$ 时，检查 $c-1$ 和 $c+1$ 是否已激活，若已激活则合并，并更新该段的最左最右。查询时直接返回该段端点。这里不再赘述细节。

---

总结

本题利用贡献法将期望拆解为每个格子乘以它成为区域最大值的概率，通过扫描线 + 数据结构维护激活区间，并利用独立乘积计算概率和，最终得到 $O(N \log N)$ 的解法。模运算处理分母 $2^N$ 的逆元即可。