https://ac.nowcoder.com/acm/contest/12548/M

题意：求静态区间数的选取集合不能构造出的和的最小值，在线


区间元素凑数性质：

如果没有1，则凑不出来的最小数为1
否则设有x个1
显然，一定可以凑出[1,x]
注意到如果剩余大于1的数中最小数为k，若k<=x+1
则可以凑出[1,x+k]

推知若当前可以凑出[1,x]，剩余数中所有小于等于x+1的数，均可累加到连续上限中
即凑出[1,x+Σsi(si<=x+1)]
若找不到新增的数，则答案为x+1。

主席树维护区间小于等于某个数的和，可以不初始化直接边插入边建树



#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;
const int N = 1e6+10,inf = 1e9;

int n,m,idx,root[N];

struct Node{
    int l,r;
    int sum;
}tr[N*50];

int insert(int p,int l,int r,int x){
    int q=++idx;
    tr[q]=tr[p];
    if(l==r){
        tr[q].sum+=x;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);
    else tr[q].r=insert(tr[p].r,mid+1,r,x);
    tr[q].sum=tr[tr[q].l].sum+tr[tr[q].r].sum;
    return q;
}

int query(int q,int p,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return tr[q].sum-tr[p].sum;
    if(l>qr||r<ql) return 0;
    int mid=l+r>>1;
    return query(tr[q].l,tr[p].l,l,mid,ql,qr)+query(tr[q].r,tr[p].r,mid+1,r,ql,qr);
}

signed main(){
    cin>>n>>m;

    for(int i=1,t;i<=n;i++){
        cin>>t;
        root[i]=insert(root[i-1],0,inf,t);
    }

    int res=0;

    while(m--){
        int l,r;
        cin>>l>>r;
        l=(res+l)%n+1,r=(res+r)%n+1;
        if(l>r) swap(l,r);
        int x=query(root[r],root[l-1],0,inf,1,1);
        int last=x;
        while(1){
            int sum=query(root[r],root[l-1],0,inf,1,min(inf,x+1))-last;
            if(!sum) break;
            x+=sum,last=x;
        }
        res=x+1;
        cout<<res<<endl;
    }

    return 0;
}