题解同各神犇的方法。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; int n,a[maxn],b[maxn],m,l,r,len,tot=0,regis; int ls[maxn*20],rs[maxn*20],sum[maxn*20],root[maxn]; void build(int &now,int left,int right) { now=++tot;sum[now]=0; if (left==right) return; int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } void modify(int last,int &now,int left,int right,int pos) { now=++tot;sum[now]=sum[last]+b[pos]; ls[now]=ls[last];rs[now]=rs[last]; if (left==right) return; int mid=(left+right)>>1; if (pos<=mid) modify(ls[last],ls[now],left,mid,pos); else modify(rs[last],rs[now],mid+1,right,pos); } int ask(int last,int now,int left,int right,int lim) { if (left==right) { if (b[left]<=lim) return sum[now]-sum[last]; else return 0; } int mid=(left+right)>>1,r=b[mid],k1=sum[ls[now]],k2=sum[ls[last]]; if (r<=lim) return sum[ls[now]]-sum[ls[last]]+ask(rs[last],rs[now],mid+1,right,lim); else return ask(ls[last],ls[now],left,mid,lim); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); len=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b; build(root[0],1,len); for (int i=1;i<=n;i++) { regis=b[a[i]]; modify(root[i-1],root[i],1,len,a[i]); } scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d%d",&l,&r); int ans=0; for (;;) { int ret=ask(root[l-1],root[r],1,len,ans+1); if (ret<ans+1) {printf("%d ",ans+1);break;} ans=ret; } } return 0; }