题解：P4587 [FJOI2016] 神秘数

Sliarae · 2025-07-22 21:49:50 · 题解

考虑给定一个集合 S，它的神秘数怎么算。

我们维护这样一个过程：设置一个变量 \text{now}，表示此时 [0, \text{now}] 之间的数都可以被表示，而 \text{now} + 1 不行。每次拿出 S 的最小元素 x 并将其从 S 中删去，并考虑 x 对 \text{now} 的影响：

• 若 x > \text{now} + 1，因为 x 已经是此时 S 中最小的数，所以 \text{now} + 1 这个数无论如何都无法被表示，直接退出。

• 若 x \le \text{now} + 1，考虑如果选了 x，因为原本 [0, \text{now}] 中的数都能被表示，所以现在 [x, x + \text{now}] 中的数也能被表示了，于是现在能表示的数的范围是 [0, x + \text{now}]。相当于做 \text{now} \gets \text{now} + x，并继续考虑下一个 x。

最终 \text{now} + 1 就是集合 S 的神秘数。

考虑将序列 a 中的所有数按数值分成若干段，每一段的值域形如 [2^k, 2^{k + 1})。具体而言，第一段值域为 [1, 2)，第二段值域为 [2, 4)，第三段值域为 [4, 8)，依次类推。

这样段数显然只有 O(\log V)，其中 V = \max a_i。考虑从小到大依次考虑每一段，假设某一段值域为 [2^k, 2^{k + 1})。找到这一段中最小的元素 x：

• 如果 x \le \text{now} + 1，那么做 \text{now}' \gets \text{now} + x，此时考虑段中的下一个数 x'，由于 x' < 2^{k + 1} - 1，一定有 x' \le \text{now}' + 1 = \text{now} + x + 1。这说明若 [2^k, 2^{k + 1} - 1) 中的任意一个数可以加入 \text{now}，则所有数都可以加入 \text{now}。

• 如果 x > \text{now} + 1，那么没有数可以加入 \text{now}。

于是只要维护：如果 [2^k ,2^{k + 1}) 中的数的最小值 \le \text{now} + 1，那么将 \text{now} 加上所有 [2^k ,2^{k + 1}) 中的数。

考虑将询问离线，从小到大扫描 k，对于每次询问，要查询一次区间和，与一次 RMQ。区间和可以简单前缀和做到 O(n) - O(1)。

对于 RMQ 的部分，朴素实现会带 \log，但是注意到每个 a_i 只会在一个 [2^k ,2^{k + 1}) 中出现，所以对于每个 k，只对有用的数建 ST 表，这样所有 ST 表的大小总和就是 O(n) 的。

总时间复杂度 O((n + q) \log V + n \log n)，空间复杂度 O(n \log n)。

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5 + 5;
const int M = 17;

int n, m, len;
int a[kN], s[kN], pre[kN], nxt[kN], ls[kN], id[kN], st[kN][M];
int l[kN], r[kN], now[kN];

int Query_min (int l, int r) {
    int k = log2(r - l + 1);
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i) cin >> l[i] >> r[i];
    for (int w = 0; w < 30; ++w) {
        nxt[n + 1] = n + 1, len = 0; 
        for (int i = 1; i <= n; ++i) {
            if ((1 << w) <= a[i] && a[i] < (1 << (w + 1))) {
                pre[i] = i;
                s[i] = s[i - 1] + a[i];
                ls[++len] = i;
                id[i] = len;
                st[len][0] = a[i];
            }
            else {
                pre[i] = pre[i - 1]; 
                s[i] = s[i - 1];
            }
        }
        for (int i = n; i; --i) {
            if (pre[i] == i) nxt[i] = i;
            else nxt[i] = nxt[i + 1]; 
        }
        for (int k = 1; k <= log2(len); ++k) {
            for (int i = 1; i + (1 << k) - 1 <= len; ++i) {
                st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
            }
        }
        for (int i = 1; i <= m; ++i) {
            int l = nxt[::l[i]], r = pre[::r[i]];
            if (l <= r && Query_min(id[l], id[r]) <= now[i] + 1) {
                now[i] += s[r] - s[l - 1];
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        cout << now[i] + 1 << '\n';
    }
    return 0; 
}