自动搬运

查看原文

来自洛谷，原作者为

	何俞均 这个人懒得一匹，什么玩意儿都没留下

搬运于2025-08-24 22:01:40，当前版本为作者最后更新于2019-01-22 15:45:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

广告：食用$blog$体验更佳

首先我们想一想暴力怎么做

对于一段区间$[l,r]$

我们先将它之间的数升序排序

从左往右扫，

设当前我们可以表示出的数为$[1,x]$,待插入的数为$a_i$

会有下面两种情况：

1.$a_i> x+1$时，$x+1$肯定表示不出来$ans=x+1$

2.$a_i\leq x+1$时，值域变为$[1,x+a_i]$，继续扫

那么我们暴力的复杂度为$O(nmlogn)$

考虑怎么优化这个过程

还是用刚才的思路

设当前值域$[1,x]$

则$ans=x+1$

若小于等于$ans$的数的和$res\geq ans$，则一定有未选的且小于等于$ans$的数，

令$ans=res+1$即可。

反之说明答案就是$ans$，直接$break$

因为有$\sum a_i\leq 10^9$,用主席树维护

所以复杂度$O(m(logn)(log\sum a_i))$

代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std; 
inline int gi() { 
    register int data = 0, w = 1; 
    register char ch = 0; 
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
}
const int MAX_N = 1e5 + 5; 
const int INF = 1e9; 
struct Node { int ls, rs, v; } t[MAX_N << 5]; 
int rt[MAX_N], tot = 0; 
void insert(int &o, int p, int l, int r, int pos, int v) { 
    o = ++tot, t[o] = t[p], t[o].v += v; 
    if (l == r) return ; 
    int mid = (l + r) >> 1; 
    if (pos <= mid) insert(t[o].ls, t[p].ls, l, mid, pos, v); 
    else insert(t[o].rs, t[p].rs, mid + 1, r, pos, v); 
} 
int query(int v, int u, int l, int r, int ql, int qr) { 
    if (ql <= l && r <= qr) return t[u].v - t[v].v; 
    int mid = (l + r) >> 1, res = 0; 
    if (ql <= mid) res += query(t[v].ls, t[u].ls, l, mid, ql, qr); 
    if (qr > mid) res += query(t[v].rs, t[u].rs, mid + 1, r, ql, qr); 
    return res; 
} 
int N, a[MAX_N]; 
int main () { 
    N = gi(); for (int i = 1; i <= N; i++) a[i] = gi(); 
    for (int i = 1; i <= N; i++) insert(rt[i], rt[i - 1], 1, INF, a[i], a[i]); 
    int M = gi();
    while (M--) { 
        int l = gi(), r = gi(), ans = 1; 
        for (;;) { 
            int res = query(rt[l - 1], rt[r], 1, INF, 1, ans); 
            if (res >= ans) ans = res + 1; 
            else break; 
        } 
        printf("%d\n", ans); 
    } 
    return 0; 
}