Luogu

分析

先考虑暴力怎么做。把 $[l, r]$ 中的数排序，然后维护 $lim$ 表示 $[1, lim]$ 中的数都能被表示出。假设当前加入了 $w$，那么

• 如果 $w > lim + 1$，则 $lim + 1$ 不能被表示出，答案即为 $lim + 1$；
• 否则更新 $lim$ 为 $lim + w$。

考虑优化。设上一次的 $lim$ 为 $pre$，那么只有 $[pre + 1, lim + 1]$ 中的数会影响当前的 $lim$，全部加进去即可。这样子需要支持求区间内 $[l, r]$ 中数的和，主席树即可。

考虑复杂度。可以发现每次 $lim$ 都至少乘 $2$，所以复杂度 $\mathcal{O}(m \log^2 A)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 100000 + 10, L = 1e9;

int n, m, a[N];

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
int rt[N], tot = 0;
int ch[N * 40][2], sum[N * 40];

void modify(int &o, int l, int r, int p, int w) {
    ++tot, ls(tot) = ls(o), rs(tot) = rs(o), sum[tot] = sum[o];
    o = tot, sum[o] += p * w;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (p <= mid) modify(ls(o), l, mid, p, w);
    else modify(rs(o), mid + 1, r, p, w);
}
int query(int x, int y, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[y] - sum[x];
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res += query(ls(x), ls(y), l, mid, ql, qr);
    if (qr > mid) res += query(rs(x), rs(y), mid + 1, r, ql, qr);
    return res;
}
#undef ls
#undef rs

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i)
        rt[i] = rt[i - 1], modify(rt[i], 1, L, a[i], 1);
    m = read();
    while (m--) {
        int l = read(), r = read();
        int lim = 0, pre = 0, s = 0;
        while (1) {
            s = query(rt[l - 1], rt[r], 1, L, pre + 1, lim + 1);
            if (!s) break;
            pre = lim + 1, lim += s;
        }
        printf("%d\n", lim + 1);
    }
    return 0;
}