现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间l,r，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。输出最小的不可由该集合所构成的数
看到区间很明显是主席树
#include<bits/stdc++.h> using namespace std; #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 ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int T[N],lson[N<<5],rson[N<<5],t[N<<5],n,m,ncnt; void upnode(int x,int l,int r,int pre,int &pos) { pos=++ncnt; t[pos]=t[pre]+x;lson[pos]=lson[pre];rson[pos]=rson[pre]; if(l==r)return ;int m=(l+r)>>1; if(x<=m)upnode(x,l,m,lson[pre],lson[pos]); else upnode(x,m+1,r,rson[pre],rson[pos]); } int qsum(int L,int R,int l,int r,int pre,int pos) { if(L<=l&&r<=R)return t[pos]-t[pre]; int m=(l+r)>>1,ans=0; if(L<=m)ans+=qsum(L,R,l,m,lson[pre],lson[pos]); if(R>m)ans+=qsum(L,R,m+1,r,rson[pre],rson[pos]); return ans; } int main() { int n;cin>>n;int x,l,r,ans,res,m; rep(i,1,n)scanf("%d",&x),upnode(x,1,1e9,T[i-1],T[i]); scanf("%d",&m); while(m--) { scanf("%d%d",&l,&r); ans=1; while(1) { res=qsum(1,ans,1,1e9,T[l-1],T[r]); if(res>=ans)ans=res+1; else break; } printf("%d ",ans); } return 0; }