这题开始的思路就是模拟：就像数组中插点一样，每一个想买票的人都想往前插队！但是这样的话肯定TLE， 看了别人的思路之后才恍然大悟！正解：    将开始的正序插入，变成倒序插入，这样的话，想一想：第 i 个人想要插在 p[i]    的位置上，那么就要保证所插入的位置之前一定要有 p[i]-1个空位！因为一定会有p[j]

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define M 200005 6 using namespace std; 7  8 pair
         
          per[M]; 9 int ret[M]; 10 int tree[M*4];11 int n;12 13 void buildT(int p, int ld, int rd){14     if(ld==rd){15         tree[p]=1;16         return ;17     }18     int mid=(ld+rd)>>1;19     buildT(p<<1, ld, mid);20     buildT(p<<1|1, mid+1, rd);21     tree[p]=tree[p<<1]+tree[p<<1|1]; 22 }23 24 void updateT(int p, int ld, int rd, int pos, int val){25    if(ld==rd){26       tree[p]=0;27       ret[ld]=val;28       return ;29    }30    int mid=(ld+rd)>>1;31    if(tree[p<<1]>pos)32       updateT(p<<1, ld, mid, pos, val);33    else 34       updateT(p<<1|1, mid+1, rd, pos-tree[p<<1], val);35       36    tree[p]=tree[p<<1]+tree[p<<1|1]; 37 }38 39 int main(){40    int i;41    while(scanf("%d", &n)!=EOF){42       buildT(1, 1, n); 43       for(i=1; i<=n; ++i)44          scanf("%d%d", &per[i].first, &per[i].second);45       for(i=n; i>=1; --i)46          updateT(1, 1, n, per[i].first, per[i].second);47 48       printf("%d", ret[1]);49       for(i=2; i<=n; ++i)50          printf(" %d", ret[i]);51       printf("\n");  52    }53    return 0;54 }
         
        
       
      
     

 

1 //树状数组～～不解释 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6  7 #define N 200005 8 using namespace std; 9 10 int tree[N];11 int pos[N], val[N];12 int ret[N];13 int n;14 15 int lowbit(int x){16     return x&(-x);17 }18 19 void buildT(){20     for(int i=1; i<=n; ++i){21         tree[i]=0;22         for(int j=i-lowbit(i)+1; j<=i; ++j)23             tree[i]+=1;24     }25 }26 27 void updateT(int x){28     while(x<=n){29         tree[x]-=1;30         x+=lowbit(x);31     }32 }33 34 int getSum(int x){35     int s=0;36     while(x>0){37         s+=tree[x];38         x-=lowbit(x);    39     }40     return s;41 }42 43 int main(){44     while(scanf("%d", &n)!=EOF){45         buildT(); 46         for(int i=1; i<=n; ++i){47             scanf("%d%d", &pos[i], &val[i]);48             ret[i]=-1;49         }50         for(int i=n; i>=1; --i){51             int ld=1, rd=n;52             bool flag=false;53             while(ld<=rd){54                 int mid=(ld+rd)>>1;55                 int s=getSum(mid);56                 //如果当前的位置没有人插入并且该位置的之前的人数恰好为pos[i] 57                 if(ret[mid]==-1 && s==pos[i]+1){ 58                     updateT(mid);59                     ret[mid]=val[i];60                     flag=true;//已经找到不用在继续寻找了 61                     break;62                 }63                 else if(s>=pos[i]+1)64                     rd=mid-1;65                 else ld=mid+1;66             }67             if(!flag) ret[rd+1]=val[i];//直到找到当前的位置没有人插入并且该位置的之前的人数恰好为pos[i]  68         }69         printf("%d", ret[1]);70         for(int i=2; i<=n; ++i)71              printf(" %d", ret[i]);72         printf("\n"); 73     } 74     return 0; 75 }