题目大意：给你一个序列，对于每个i，你可以选择1~i-1中任意多的数并将它删去，剩余的数（包括i）∑≤m，问对于每个i最少删几个数可以达到要求

题解：

考虑朴素的思想，对于每个i，我只需要删去最大的若干个使得∑≤m即可，时间复杂度O(n^2)

显然不可接受，考虑优化

显然可以看出，因为只需要删去最大的若干数，于是想到前K大，于是很自然想到用线段树

先离散化，只需要记录这个数是第几大，之后线段树维护区间和，每新加入一个点时加入这个点第几大的下标

询问时在线段树上二分出前K大即可，时间复杂度O(nlogn)

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long longusing namespace std;int TT,n;int ans[200001];ll m;struct node{ ll v; int bh,rk;}a[200001];bool cmp(const node &T1,const node &T2){ return T1.v
            
             >1; int t=ask(l,mid,v,pos<<1,tot); if(t==cnt[pos<<1])t+=ask(mid+1,r,v,pos<<1|1,tot+sum[pos<<1]); return t; }}void insert(int l,int r,ll v,int p,int pos){ if(l==r && l==p) { sum[pos]=v;cnt[pos]=1; return; } int mid=l+r>>1; if(p<=mid)insert(l,mid,v,p,pos<<1); else insert(mid+1,r,v,p,pos<<1|1); sum[pos]=sum[pos<<1]+sum[pos<<1|1]; cnt[pos]=cnt[pos<<1]+cnt[pos<<1|1];}int main(){ scanf("%d",&TT); while(TT--) { memset(sum,0,sizeof(sum)); memset(cnt,0,sizeof(cnt)); memset(ans,0,sizeof(ans)); scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++){scanf("%lld",&a[i].v);a[i].bh=i;} sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++)a[i].rk=i; sort(a+1,a+1+n,cmp2); for(int i=1;i<=n;i++) { int t=ask(1,n,m-a[i].v,1,0); ans[i]=i-1-t; insert(1,n,a[i].v,a[i].rk,1); } for(int i=1;i<=n;i++)printf("%d ",ans[i]); printf("\n"); } return 0;}
            
           
          
         
        
       
      
     

心得：考场上很自然的想到，说明该部分知识掌握不错，继续加油