bzoj4299

主席树+脑洞

首先我们有一个结论：如果我们已经凑出1-n,那么下一个数必须小于等于n+1才能凑出n+1，否则结束。

那么如果只有一次询问，我们把数组排序，然后扫一遍看每个数当前能不能加入。但是多组询问就不行了，这是我们就要用主席树。

主席树是权值线段树，我们维护区间和，但是我们不能扫一遍，就得进一步优化。

我们发现每次我们找<=n+1的数的和必须>上一次的结果才满足，否则退出，那么我们构造一个最小，发现是斐波那契数列，就是logn，每次主席树查找权值和就行了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

int n, m, cnt, lim;

int lc[N], rc[N], root[N], x[N];

ll sum[N];

void update(int l, int r, int last, int &x, int pos)

{

    x = ++cnt;

    sum[x] = sum[last] + pos;

    if(l == r) return;

    int mid = (l + r) >> ;

    lc[x] = lc[last];

    rc[x] = rc[last];

    if(pos <= mid) update(l, mid, lc[last], lc[x], pos);

    else update(mid + , r, rc[last], rc[x], pos);

}

ll query(int l, int r, int x, int y, int k)

{

    if(l == r)

    {

        if(k >= l) return sum[y] - sum[x];

        else return ;

    }

    int mid = (l + r) >> ;

    if(k <= mid) return query(l, mid, lc[x], lc[y], k);

    else return sum[lc[y]] - sum[lc[x]] + query(mid + , r, rc[x], rc[y], k);

}

void build(int l, int r, int &x)

{

    if(l > r) return;

    x = ++cnt;

    if(l == r) return;

    int mid = (l + r) >> ;

    build(l, mid - , lc[x]);

    build(mid + , r, rc[x]);

}

int main()

{

    scanf("%d", &n);

    build(, n, root[]);

    for(int i = ; i <= n; ++i)

    {

        scanf("%d", &x[i]); lim = max(lim, x[i]);

    }

    for(int i = ; i <= n; ++i)

        update(, lim, root[i - ], root[i], x[i]);

    scanf("%d", &m);

    while(m--)

    {

        int l, r; ll S = ; scanf("%d%d", &l, &r);

        for(; ;)

        {

            ll t = query(, lim, root[l - ], root[r], S);

            if(t == S - )

                break;

            else

                S = t + ;

        }

        printf("%lld\n", S);

    }

    return ;

}