题目链接

题意：给定了n堆石子每堆的数量是[1,1e9]的整数，q次询问，每次给出区间[l,r]，可以选择[l,r]区间的石子堆加起来凑出一个数x，问最小的无法被凑出的数是多少？
（每次询问中，每堆石子最多选择1次，此题强制在线）

分析：
对于[l,r]区间，我们把石子数放进一个桶里。
首先0肯定可以被凑到，因为可以每堆都不选。
此时我们关心1是否能被凑到,我们查询桶内 值在[0,1]区间的数的和，
假设和为x,(也就是有x个1), 那么说明我们可以凑出[0,x]区间的所有数

(当然，如果此时x的值是0，那么说明1不能被凑到,算法退出,答案就是1)

于是关心x+1能否被凑到,我们查询桶内 值在[0,x+1]区间的数的和，
假设和为x1，设[0,x+1]没有参与合成x的数的和为sum,
那么有x+sum=x1,由于我们已经可以凑出[0,x]的每个数了，所以我们可以凑出[0,x+sum]的每个数。 次数如果sum==0，那么说明x+1无法被凑出。

思路：建主席树维护桶的区间和。 每次取出root[r]-root[l-1]这棵树，查询区间和。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn = 1e6+10;
const int mx = 31;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
//给定整数数列  每次询问一个区间[l,r] 选取这个区间的一个子区间凑成一个数  问最小的无法被凑出的数x是多少
//主席树 维护桶的区间和  查询区间和
ll tree[maxn*mx];
int lc[maxn*mx],rc[maxn*mx],root[maxn],cnt=0;
inline void updata(int &rt,int last,int l,int r,int x)
{
    rt=++cnt;
    tree[rt]=tree[last]+x;
    lc[rt]=lc[last],rc[rt]=rc[last];
    if(l == r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) updata(lc[rt],lc[last],l,mid,x);
    else updata(rc[rt],rc[last],mid+1,r,x);
}
inline ll query(int rt1,int rt2,int l,int r,ll vr )
{
    if(1<= l && r<=vr) return tree[rt1]-tree[rt2];
    int mid=(l+r)>>1;
    if(vr<=mid) return query(lc[rt1],lc[rt2],l,mid,vr);
    if(1>mid) return query(rc[rt1],rc[rt2],mid+1,r,vr);
    return query(lc[rt1],lc[rt2],l,mid,vr)+query(rc[rt1],rc[rt2],mid+1,r,vr);
}
int n,q;
int main()
{
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        updata(root[i],root[i-1],1,INF,x);
    }
    ll ans=0;
    int l,r;
    while(q--)
    {
        scanf("%d %d",&l,&r);
        l=(l+ans)%n+1;
        r=(r+ans)%n+1;
        if(l>r) swap(l,r);
        ans=0;//假设已经扩展到[0,ans] 查询[0,ans+1]桶内所有元素的和t 是否大于ans  如果是 那么可以凑出[0,t]
        while(1)
        {
            ll t=query(root[r],root[l-1],1,INF,ans+1);
            if(t==ans) break;//无法凑出ans+1这个数
            ans=t;
        }
        printf("%lld\n",++ans);
    }
    return 0;
}