BZOJ4299 Codechef FRBSUM（主席树）

　　感觉非常不可做，于是考虑有什么奇怪的性质。

　　先考虑怎么求子集和mex。将数从小到大排序，假设已经凑出了0~n的所有数，如果下一个数>n+1显然mex就是n+1了，否则若其为x则可以凑出1~n+x所有数。

　　对于区间查询，建棵主席树即可，每次查询权值线段树上lastn+2~n+1的区间，用区间和更新n，如果这段区间没有数则mex为n+1。因为每次n的增量都是在lastn+2~n+1这一段的，所以每查询两次n会翻一倍以上，复杂度O(nlogn)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define inf 1000000000

int n,m,a[N],root[N],cnt;

struct data{int l,r,x;

}tree[N<<];

void ins(int &k,int l,int r,int x)

{

    tree[++cnt]=tree[k],k=cnt;tree[k].x+=x;

    if (l==r) return;

    int mid=l+r>>;

    if (x<=mid) ins(tree[k].l,l,mid,x);

    else ins(tree[k].r,mid+,r,x);

}

int query(int x,int y,int l,int r,int p,int q)

{

    if (!y) return ;

    if (p==l&&q==r) return tree[y].x-tree[x].x;

    int mid=l+r>>;

    if (q<=mid) return query(tree[x].l,tree[y].l,l,mid,p,q);

    else if (p>mid) return query(tree[x].r,tree[y].r,mid+,r,p,q);

    else return query(tree[x].l,tree[y].l,l,mid,p,mid)+query(tree[x].r,tree[y].r,mid+,r,mid+,q);

}

int getans(int l,int r)

{

    int sum=,last=-;

    while (sum<inf)

    {

        int x=query(root[l],root[r],,inf,last+,sum+);

        if (!x) return sum+;

        else last=sum,sum+=x;

    }

    return sum;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4299.in","r",stdin);

    freopen("bzoj4299.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

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

    {

        root[i]=root[i-];

        ins(root[i],,inf,a[i]);

    }

    m=read();

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

    {

        int x=read(),y=read();

        printf("%d\n",getans(x-,y));

    }

    return ;

}