题意：
每次可以用[ l , r ] [l,r][l,r]的子集来凑数，问最小无法凑出的数。
强制在线
思路：
如果当前区间没有1,那么答案肯定为1
假设当前有t个1，那么可以凑出[ 1 , t ]
假设1之后最小的数是z
那么如果z > t + 1，说明t + 1就是答案；
否则，能够凑出[ 1 , t + z ]，继续上述过程
所以对于每次的区间[ 1 , t ]，都要找出小于t + 1的数字的和减去构成[ 1 , t ]的数的和，如果为0说明t + 1就是答案，否则就继续寻找；
借助主席树实现上述操作，维护某段区间的和。
代码
// Problem: Stone Games // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/14055/M // Memory Limit: 2097152 MB // Time Limit: 8000 ms // Author:Cutele // // Powered by CP Editor (https://cpeditor.org) //#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=1e6+7,inf=1e9,N=4e7+10; struct node{ int l,r; ll sum; }tr[N]; int root[maxn],idx,n,q,a[maxn]; void insert(int &now,int las,int l,int r,int val){ now=++idx; tr[now].l=tr[las].l,tr[now].r=tr[las].r; tr[now].sum=tr[las].sum+val; if(l==r) return ; int mid=(l+r)/2; if(val<=mid) insert(tr[now].l,tr[las].l,l,mid,val); else insert(tr[now].r,tr[las].r,mid+1,r,val); } ll query(int now,int las,int l,int r,int L,int R){ if(L<=l&&r<=R) return tr[now].sum-tr[las].sum; if(l>R||r<L) return 0ll; int mid=(l+r)/2; return query(tr[now].l,tr[las].l,l,mid,L,R)+query(tr[now].r,tr[las].r,mid+1,r,L,R); } int main(){ n=read,q=read; rep(i,1,n) a[i]=read,insert(root[i],root[i-1],0,inf,a[i]); ll las=0; while(q--){ ll l=read,r=read; l=(l+las)%n+1,r=(r+las)%n+1; if(l>r) swap(l,r); ll x=query(root[r],root[l-1],0,inf,1,1); ll now=x; while(1){ ll tmp=query(root[r],root[l-1],0,inf,1,min(x+1,inf*1ll))-now; if(tmp==0) break; x=x+tmp;now=x; } las=x+1; cout<<las<<endl; } return 0; }
