「PA 2020」Miny 题解

算法思路

本题使用动态规划结合树状数组优化和单调栈来解决地雷引爆的组合计数问题。核心思想是通过维护可达区间和利用组合数学计算不同爆炸集合的数量。

关键观察

1. 引爆传播关系

地雷 $i$ 引爆后可以传播到区间 $[L[i], R[i]]$，其中：

• $L[i] = \min\{j : a[i] - r[i] \leq a[j]\}$
• $R[i] = \max\{j : a[j] \leq a[i] + r[i]\}$

2. 组合计数原理

如果手动引爆的地雷集合为 $S$，那么最终爆炸的地雷集合是 $S$ 的传递闭包。不同的爆炸集合对应不同的连通分量选择。

代码解析

区间预处理

for (int i = 1; i <= n; i++) {
    L[i] = lower_bound(a + 1, a + n + 1, a[i] - r[i]) - a;
    R[i] = upper_bound(a + 1, a + n + 1, a[i] + r[i]) - a - 1;
}

动态规划状态

$f[i]$ 表示考虑前 $i-1$ 个地雷，且第 $i$ 个地雷是某个连通分量起点时的方案数。

树状数组优化

struct BIT {
    int c[N];
    void add(int x, int v) {
        x++;
        while (x) {
            c[x] = (c[x] + v) % P;
            x -= x & -x;
        }
    }
    
    int qry(int x) {
        x++;
        int ret = 0;
        while (x <= n + 1) {
            ret = (ret + c[x]) % P;
            x += x & -x;
        }
        return ret;
    }
} t;

主要算法流程

f[0] = 1;
set<int> in;
in.insert(0);
t.add(0, 1);
vector<int> st;  // 单调栈

for (int i = 1; i <= n + 1; i++) {
    // 使用单调栈找到能覆盖当前位置的最左起点
    int l = -1, r = (int)st.size();
    while (r - l > 1) {
        int m = (l + r) >> 1;
        if (R[st[m]] >= i) l = m;
        else r = m;
    }
    int pos = (l != -1) ? st[l] : 0;
    
    // 状态转移
    f[i] = t.qry(pos);
    
    // 维护单调栈（递减的R[i]）
    while (st.size() && R[i] >= R[st.back()])
        st.pop_back();
    st.push_back(i);
    
    if (i == n + 1) break;
    
    // 清理过期的状态
    auto it = in.lower_bound(L[i]);
    while (it != in.end()) {
        t.add(*it, (P - f[*it]) % P);
        it = in.erase(it);
    }
    
    // 添加新状态
    t.add(i, f[i]);
    in.insert(i);
}

算法正确性

状态转移方程

$f[i]$ 表示以 $i$ 作为新连通块起点时的方案数。转移时，找到能覆盖当前位置 $i$ 的最远起点 $pos$，然后：

单调栈的作用

维护一个 $R$ 值递减的栈，用于快速找到能覆盖当前位置的最左起点。

树状数组优化

支持区间求和和单点更新，将转移复杂度从 $O(n)$ 优化到 $O(\log n)$。

复杂度分析

• 预处理：$O(n \log n)$（二分查找）
• 主循环：$O(n \log n)$（每个元素入栈出栈一次，树状数组操作）
• 总复杂度：$O(n \log n)$

关键技巧

1. 区间预处理：使用二分确定每个地雷的引爆范围
2. 单调栈：快速找到覆盖关系
3. 树状数组：高效维护 DP 状态和
4. 集合维护：动态清理过期状态