它是的前置技能点

模板：

参考里的文章讲的不错呢..我就不多写了

其实维护的是一个类似桶的东西，当向集合内加入x时，就向权值线段树中位置x那里+1

查询一个数的排名，就维护权值线段树中每个点所管辖的区间里值的个数val，查询时看一下左右儿子的val就知道该向那边递归下去了，层层累加排名。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;struct ValSegTree{ int size; struct node{ int l,r,val; }tree[400005]; void build(int id,int l,int r){ tree[id]=(node){l,r,0}; if(l==r) return; int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); } int al,aval; void update(int id){ int l=tree[id].l,r=tree[id].r; if(l==r){ tree[id].val+=aval;return; } int mid=(l+r)/2; if(al<=mid) update(id*2); else update(id*2+1); tree[id].val=tree[id*2].val+tree[id*2+1].val; } int wk,rank; int afo(int id){ int l=tree[id].l,r=tree[id].r; if(l==r) return l; if(wk<=rank+tree[id*2].val){ return afo(id*2); }else{ rank+=tree[id*2].val; return afo(id*2+1); } } int ark(int id,int rk){ int l=tree[id].l,r=tree[id].r; if(l==r) return rk; int mid=(l+r)/2; if(aval<=mid) return ark(id*2,rk); else return ark(id*2+1,rk+tree[id*2].val); } //for user void init(int mys){ size=mys; build(1,1,size); } void change(int l,int val){ al=l,aval=val; update(1); } int askval(int mwk){ //返回排名第几的数 wk=mwk,rank=0; return afo(1); } int askrk(int val){ //返回前面有多少个数（rank-1） aval=val; return ark(1,0); }}seg;int qn,hn;int hash[100005];int hashfind(int key){ int l=1,r=hn; for(;;){ int mid=(l+r)/2; if(l==r){ return l; } if(hash[mid]
              
               >qn; seg.init(100005); hn=0; for(int i=1;i<=qn;i++){ scanf("%d%d",&cz[i].type,&cz[i].val); if(cz[i].type!=4){ hn++;hash[hn]=cz[i].val; } } sort(hash+1,hash+1+hn); for(int i=1;i<=qn;i++){ switch(cz[i].type){ case 1:{ int pv=hashfind(cz[i].val); seg.change(pv,1); break; }case 2:{ int pv=hashfind(cz[i].val); seg.change(pv,-1); break; }case 3:{ printf("%d\n",solve3(hashfind(cz[i].val))+1); break; }case 4:{ printf("%d\n",solve4(cz[i].val)); break; }case 5:{ int pv=solve3(hashfind(cz[i].val));//刚好求的就是前缀 printf("%d\n",solve4(pv)); break; }case 6:{ int pv=solve3(hashfind(cz[i].val)+1)+1;//solve(...)+1如果...已经在线段树内求得的是后缀排名+1，所以在hashfind后+1防止这种情况发生 printf("%d\n",solve4(pv)); break; } } } return 0;}
              
             
            
           
          
         
        
       
      

 

参考：