Poj 2182-Lost Cows（Treap||树状数组+二分答案） - c++编程基础

题目链接：点击打开链接

题意：n个牛编号为1-n 现在编号顺序已经打乱，给出a[i] ,a[i] 代表i位置前面有几个小于它的编号，求编号顺序。

倒着推，对于最后一个a[i] , 最后位置编号肯定是 a[i]+1,然后在1-n个编号中删掉当前编号，继续往前推。。即求第 a[i]+1小数，初始容器中有n个数（1-n），每求出来一个就删掉。先用平衡树水了一发。。明天写树状数组解法。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 8005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair
               
                 #define ull unsigned long long using namespace std; int n,ans[maxn]; struct node{ node *ch[2]; int r,v,s; node (){} node (int v){ch[0]=NULL;ch[1]=NULL;r=rand();this->v=v;s=1;} bool operator <(const node& c)const{ return r
                
                 s; if(ch[1]!=NULL)s+=ch[1]->s; } }; void rotate(node* &o,int d){ node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o; o->maintain();k->maintain();o=k; } void insert(node* &o,int x) { if(o==NULL) o=new node(x); else{ int d=o->cmp(x); insert(o->ch[d],x); if(o->ch[d]->r>o->r)rotate(o,d^1); } o->maintain(); } void remove(node* &o,int x) { int d=o->cmp(x); if(d==-1){ node* u=o; if(o->ch[0]!=NULL&&o->ch[1]!=NULL){ int d2=(o->ch[0]->r>o->ch[1]->r?1:0); rotate(o,d2);remove(o->ch[d2],x); } else{ if(o->ch[0]==NULL)o=o->ch[1]; else o=o->ch[0]; delete u; } } else remove(o->ch[d],x); if(o!=NULL) o->maintain(); } bool find(node* o,int x) { while(o!=NULL) { int d=o->cmp(x); if(d==-1)return 1; else o=o->ch[d]; } return 0; } int find_kth(node* o,int k) { if(o==NULL||k>o->s)return -1; int s=(o->ch[0]==NULL?0:o->ch[0]->s); if(k==s+1)return o->v; else if(k<=s) return find_kth(o->ch[0],k); else return find_kth(o->ch[1],k-s-1); } void solve() { node *root=NULL; for(int i=1;i<=n;i++) insert(root,i); for(int i=0;i
                 
                  =0;i--){ //cout<<"ans["<
                  
                   v); for(int i=0;i<=n-2;i++) printf("%d\n",ans[i]); } int main() { while(~scanf("%d",&n)) solve(); return 0; }