问区间的数不能加出来的数的最小值。
感觉挺难的。
主要是有一条性质很重要,当前可以凑到的数是mx,那么假如加入一个
然后就可以主席树乱搞了,因为每次至少扩大一倍,所以是
code:
#include#include #include #include using namespace std; int inf=1000000010; int n; struct trnode{ int lc,rc,c; }tr[3500000];int tot=0,root[100010]; void update(int &x,int fx,int l,int r,int k) { x=++tot;tr[x]=tr[fx]; if(l==r) {tr[x].c+=k;return;} int mid=(l+r)/2; if(k<=mid) update(tr[x].lc,tr[fx].lc,l,mid,k); else update(tr[x].rc,tr[fx].rc,mid+1,r,k); tr[x].c=tr[tr[x].lc].c+tr[tr[x].rc].c; } int findans(int lx,int rx,int l,int r,int fl,int fr) { if(l==fl&&r==fr) return tr[rx].c-tr[lx].c; int mid=(l+r)/2; if(fr<=mid) return findans(tr[lx].lc,tr[rx].lc,l,mid,fl,fr); if(fl>mid) return findans(tr[lx].rc,tr[rx].rc,mid+1,r,fl,fr); return findans(tr[lx].lc,tr[rx].lc,l,mid,fl,mid)+findans(tr[lx].rc,tr[rx].rc,mid+1,r,mid+1,fr); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); update(root[i],root[i-1],1,inf,x); } int m;scanf("%d",&m); while(m--) { int l,r;scanf("%d %d",&l,&r); int sum=0,la=0; while(1) { int tmp=findans(root[l-1],root[r],1,inf,la+1,sum+1); if(tmp==0) break; la=sum+1;sum+=tmp; } printf("%d\n",sum+1); } }