题解：P9100 [PA2020] Miny

· · 题解

\mathcal{Link}

有神秘的分治做法，有点厉害。写个无脑做法。

定义 f_i 表示钦定 i 考虑前 i 个且钦定第 i 个不爆炸的方案数。

转移只有一种情况，假设 [j + 1, i - 1] 中的都无法引爆 i, j，就令 f_i \gets f_i + f_j。这样以后我们只需要求出一个炸弹 i 可以引爆的最右边的炸弹 r_i 和最右侧可以引爆 i 的炸弹 l_i。

这个求法只用维护一个单调栈然后二分就可以了。于是就有 f_i = \sum_{l_i}^{i - 1} f_j，这样子使用树状数组就可以了。

时间复杂度 \mathcal{O}(n \log n)。

int n, st[N], top, L[N], R[N];
ll a[N], r[N]; vector<int> buc[N];
mint c[N], f[N];

int lb(int x) { return x & -x; }
void add(int x, mint v) { for (; x < N; x += lb(x)) c[x] += v; }
mint ask(int x) { mint res(0); if(x <= 0) return res; for (; x; x -= lb(x)) res += c[x]; return res; }

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> r[i];
    a[0] = -inf, a[n + 1] = inf; f[0] = 1; add(1, 1);
    r[0] = r[n + 1] = inf * 2;
    st[top = 1] = 0; R[0] = n + 1;

    for (int i = 1; i <= n; i++) {
        auto get = [=](int u) -> ll { return a[u] + r[u]; };
        int l = 1, r = top, res = 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (get(st[mid]) >= a[i]) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        L[i] = st[res];
        while (get(i) >= get(st[top])) top--;
        st[++top] = i;
    }
    st[top = 1] = n + 1;
    for (int i = n; i >= 1; i--) {
        auto get = [=](int u) -> ll { return a[u] - r[u]; };
        int l = 1, r = top, res = 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (get(st[mid]) <= a[i]) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        R[i] = st[res];
        while (get(i) <= get(st[top])) top--;
        st[++top] = i;
    }
    auto query = [=](int l, int r) -> mint { return ask(r) - ask(l - 1); };
    for (int i = 0; i <= n; i++) buc[R[i]].emplace_back(i);
    for (int i = 1; i <= n + 1; i++) {
        f[i] = query(L[i] + 1, i);
        for (int j : buc[i]) add(j + 1, -f[j]);
        add(i + 1, f[i]);
    }
    cout << f[n + 1].x << "\n";
    return 0;
}