P4587 [FJOI2016] 神秘数题解

zyb_txdy · 2025-11-14 15:09:55 · 题解

提供一个可能不太一样的思考角度。

首先考虑什么样的数可以对答案产生贡献。

一些经典的“如何用少量的数的和表示值域内的所有数”类型问题或许能给出一些启发。这里直接给出结论：将集合内的数从小到大排序，并设 \text{pre}_i 为集合内前 i 小的数的和。此时，对于正整数 k，若存在 i 满足 \text{pre}_i < k 且 a_{i + 1} > k，则 k 可以产生贡献。证明考虑前文提到的问题即可。

进一步地，我们可以得出一个较为暴力的多项式做法：对于一次询问，将 [l, r] 内的数排序，并顺序扫描，对于下标 i（这里我们可以认为是从 1 开始），若 \text{pre}_i + 1 < a_{i + 1}，则 \text{ans} = \text{pre}_i + 1。该做法的复杂度为 O(qn \log n)，不能通过。

接下来尝试如何进一步限制可能产生贡献的位置。一个经典的角度是：若下标 i 可能产生贡献，则 a_i 与 a_{i + 1} 的值（或者说它们之间的差距）是指数级增长的。用心感受后，你可能会发现数值增长的速率约为每次 \times 2。具体的增长速率下限可能并不容易求出，不过没关系，我们可以从下面的角度思考：

考虑在值域上进行类似“二分”的操作来求答案。设当前考虑的区间为 [l, r]，则我们定义 \text{sum} 为 [l, \text{mid}] 内所有元素的和，\text{mn} 为 [\text{mid} + 1, +\infty) 内的元素的最小值。

接下来比较 \text{sum} 与 \text{mn} 的大小关系：

若 \text{sum} + 1 < \text{mn}，则用 \text{sum} + 1 更新答案。此时因为更大的数必然不可能对答案产生贡献，故我们只需递归 [l, \text{mid}] 即可。
否则，考虑 \text{sum} + \text{mn} \ge 2 \times \text{mid} - 1 > r，我们再次得出了 [\text{mid} + 1, r] 内的数不可能产生贡献的结论。因此我们仍只需递归 [l, \text{mid}]。

我们显然可以用线段树维护上文的操作过程。这题有多组询问，因此使用可持久化线段树即可。

该做法的时间复杂度为 O(n \log V + q \log^2 V)，空间复杂度为 O(n \log V)，并且不需要什么复杂的关于 \log 底数的说明。

::::info[code]

#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)

using namespace std;

constexpr int N = 1e5 + 5, INF = 2e9;

struct Segment_Tree {
    int L, R, cnt;
    int rt[N];
    struct Node {
        int l, r, sum;
    } a[N << 5];

    void push_up(int p) {
        a[p].sum = a[a[p].l].sum + a[a[p].r].sum;
    }

    void init(int n) {
        L = 1, R = n;
        rt[0] = cnt = 1;
    }

    void update(int &p, int q, int l, int r, int k) {
        a[p = ++cnt] = a[q];
        if (l == r) {
            a[p].sum += k;
            return;
        }
        if (k <= mid) {
            update(a[p].l, a[q].l, l, mid, k);
        } else {
            update(a[p].r, a[q].r, mid + 1, r, k);
        }
        push_up(p);
    }

    void update(int id, int k) {
        update(rt[id], rt[id - 1], L, R, k);
    }

    int qry(int p, int q, int l, int r) {
        if (a[q].sum - a[p].sum == 0) {
            return INF;
        }
        if (l == r) {
            return l;
        }
        if (a[a[q].l].sum - a[a[p].l].sum > 0) {
            return qry(a[p].l, a[q].l, l, mid);
        } else {
            return qry(a[p].r, a[q].r, mid + 1, r);
        }
    }

    int res, mn;
    void query(int p, int q, int l, int r) {
        if (l == r) return;
        int sum = a[a[q].l].sum - a[a[p].l].sum;
        mn = min(mn, qry(a[p].r, a[q].r, mid + 1, r));
        if (sum + 1 < mn) {
            res = sum + 1;
        }
        query(a[p].l, a[q].l, l, mid);
    }

    int query(int l, int r) {
        res = a[rt[r]].sum - a[rt[l - 1]].sum + 1, mn = 1e9;
        query(rt[l - 1], rt[r], L, R);
        return res;
    }
} ST;

int n, q;
int a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    ST.init(1e9);
    for (int i = 1; i <= n; ++i) {
        ST.update(i, a[i]);
    }

    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ST.query(l, r) << '\n';
    }

    return 0;
}

::::

P4587 [FJOI2016] 神秘数 题解

P4587 [FJOI2016] 神秘数题解