M.Stone Games

题意：每次询问给出L,R，问[L,R]中选择一个子集求和，无法凑出的最小正整数是多少；

思路：首先，如果没有1，那么;
假设现在能组成，且内有，那么就能凑出，即凑出,然后继续凑;
反之若内不存在，则无法凑出的最小正整数就是
x的增长速度是指数级的，因此最多次就出来了。

询问两个区间总和之差，需要用区间权值线段树，即可持久化线段树
复杂度:

记录的是第个版本的线段树，每次建个新的线段树需要重新开个点。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+7,maxm=2e5+7,N=1e5+7;
typedef long long int ll;
typedef unsigned long long ull;
struct node{
    int lt,rt;
    ll sum;
}t[maxn*31];
int tot;
void modify(int &x,int l,int r,int v) {
    t[++tot]=t[x];
    x=tot;
    t[x].sum+=v;
    if(l==r) return;
    int mid=l+r>>1;
    if(v<=mid) modify(t[x].lt,l,mid,v);
    else modify(t[x].rt,mid+1,r,v);
}
ll query(int x,int y,int l,int r,ll v) {
    if(l==r) return t[x].sum-t[y].sum;
    int mid=l+r>>1;
    if(v<=mid) return query(t[x].lt,t[y].lt,l,mid,v);
    else return query(t[x].rt,t[y].rt,mid+1,r,v)+ t[t[x].lt].sum - t[t[y].lt].sum;
}
int rt[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,Q,l,r;
    ll ans(0),tmp;
    cin>>n>>Q;
    for(int i=1,x;i<=n;++i) {
        cin>>x;
        modify(rt[i]=rt[i-1],1,1000000000,x);
    }
    while(Q--) {
        cin>>l>>r;
        l=(ans+l)%n+1;
        r=(ans+r)%n+1;
        if(l>r) swap(l,r);
        ans=0;
        while(true) {
            tmp=query(rt[r],rt[l-1],1,1000000000,ans+1);
            if(tmp==ans) break;
            ans=tmp;
        }
        cout<<++ans<<'\n';
    }
    return 0;;
}