题意：有n个人排队买票，每个人的位置为pos(0~n-1),价值是val，如果位置相同，来的晚的人可以插入他选的位置。最后输出队列中的val。

1 #include 
      
        2 #include 
       
         3 const int N=200010; 4 int Tree[N*4],seq[N]; 5 int pos[N],val[N]; 6  7 void build(int l,int r,int rt) 8 { 9     Tree[rt]=r-l+1;//初始每个区间的空位数10     if(l==r)11         return;12     int mid=(l+r)>>1;13     build(l,mid,2*rt);14     build(mid+1,r,2*rt+1);15 }16 void update(int p,int v,int l,int r,int rt)17 {18     Tree[rt]--;//每更新一次空位数-119     if(l==r)20     {21         seq[l]=v;//将value放在l位置中22         return ;23     }24     int mid=(l+r)>>1;25     if(Tree[2*rt] >= p)//左区间的空位数量够26         update(p,v,l,mid,2*rt);//更新左区间27     else    //左区间的空位数量不够，则p在右区间28     {29         p-=Tree[2*rt];//减去左区间的空位30         update(p,v,mid+1,r,2*rt+1);//更新右区间31     }32 }33 int main()34 {35     int n;36     while(~scanf("%d",&n))37     {38         build(1,n,1);39         for (int i = 1; i <= n; i++)40         {41             scanf("%d%d",&pos[i],&val[i]);42             pos[i]++;43         }44         for (int i = n; i > 0; i--)//倒着更新，因为来的越晚的人越有利于占据pos位置45         {46             update(pos[i],val[i],1,n,1);47         }48         for (int i = 1; i <= n; i++)49         {50             if (i==1)51                 printf("%d",seq[i]);52             else53                 printf(" %d",seq[i]);54         }55         puts("");56     }57     return 0;58 }