题目链接：

题意：

题解：

对给的n个数做差分，即a[i]=a[i]-a[i-1]，然后对做完差分之后的数组从后往前扫一遍（最后一个数就是代表整个序列中比它大的数有a[n-1]个，即，它是第a[n-1]+1大的数），每次求还未求出的数中的第（a[i]+1）大(第1大就是最大的意思)。

代码：

线段树：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define lson (o<<1) 5 #define rson ((o<<1)|1) 6 #define M (l+(r-l)/2) 7 using namespace std; 8  9 const int maxn=50000+10;10 11 int n,arr[maxn],ans[maxn];12 13 int sumv[maxn<<2];14 15 void build(int o,int l,int r){16     if(l==r){17         sumv[o]=1;18     }else{19         build(lson,l,M);20         build(rson,M+1,r);21         sumv[o]=sumv[lson]+sumv[rson];22     }23 }24 25 int _ret;26 void query(int o,int l,int r,int k){27     if(l==r){28         _ret=l;29         sumv[o]=0;30     }else{31         if(sumv[rson]>=k) query(rson,M+1,r,k);32         else query(lson,l,M,k-sumv[rson]);33         sumv[o]=sumv[lson]+sumv[rson]; 34     }35 }36 37 int main(){38     int tc;39     scanf("%d",&tc);40     while(tc--){41         scanf("%d",&n);42         build(1,1,n);43         for(int i=0;i
        
         0;i--) arr[i]-=arr[i-1]; 45         for(int i=n-1;i>=0;i--){46             query(1,1,n,arr[i]+1);47             ans[i]=_ret;48         }49         for(int i=0;i
        
       
      
     

二分+树状数组：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define M (low+(hig-low)/2) 6 using namespace std; 7  8 const int maxn=50000+10; 9 10 int n,arr[maxn],ans[maxn];11 12 int sumv[maxn];13 14 void add(int p,int x){15     while(p<=n){16         sumv[p]+=x;17         p+=p&(-p);18     }19 }20 21 int sum(int p){22     int ret=0;23     while(p>0){24         ret+=sumv[p];25         p-=p&(-p); 26     }27     return ret;28 }29 //lower_bound30 int solve(int k){31     int low=0,hig=n;32     while(low+1
         
          0;i--) arr[i]-=arr[i-1]; 53         for(int i=n-1;i>=0;i--){54             ans[i]=solve(i+1-arr[i]);55         }56         for(int i=0;i