题目链接：

类似的题目：

测试数据：

in：

4

0 77

1 51

1 33

2 69

4

0 20523

1 19243

1 3890

0 31492

out：

77 33 69 51

31492 20523 3890 19243

题目分析：直接倒着进行插入，然后按照从前向后寻找空位进行插入：

【题解】：

　　　　线段树节点中保存这一段中的空位数，然后倒序对pos插入：

　　　　例如：　　0 77

　　　　　　　　　1 51

　　　　　　　　　1 33

　　　　　　　　　2 69

　　  先取： 2 69　　——  ——  —69—   ——   （需要前面有3个空位才能插入）

       然后取： 1 33   ——   —33—    —69—    ——   （需要前面有2个空位才能插入）

       然后取： 1 51   ——   —33—    —69—    —51—   （需要前面有2个空位才能插入）  前面只有1个空位  故插入后面空格

　 　然后取： 0 77   —77—   —33—    —69—    —51—   （需要前面有1个空位才能插入）

AC代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 const int N = 200010;10 int T,tot;11 int pre[N],vis[N];12 struct TT13 {14 int x,y;15 }a[N];16 int lowbit(int x)17 {18 return x&(-x);19 }20 void init()21 {22 for(int i=1;i<=T;i++)23 vis[i] =lowbit(i);24 }25 int sum(int x)26 {27 int ans = 0;28 while(x>0)29 {30 ans = ans+vis[x];31 x = x-lowbit(x);32 }33 return ans;34 }35 int update(int x)36 {37 while(x<=T)38 {39 vis[x] = vis[x] - 1;40 x = x +lowbit(x);41 }42 }43 void add(int x,int y)44 {45 int l=1,r=T,mid;46 while(l
            
             =x) r = mid;51 else l = mid+1;52 }53 //printf("l = %d\n",l);54 update(l);55 pre[l] = y;56 }57 int main()58 {59 int aa,bb;60 while(~scanf("%d",&T))61 {62 init();63 for(int i=1;i<=T;i++)64 {65 scanf("%d %d",&aa,&bb);66 a[i].x = aa+1;67 a[i].y = bb;68 }69 for(int i=T;i>0;i--)70 add(a[i].x,a[i].y);71 for(int i=1;i<=T;i++)72 {73 if(i==1) printf("%d",pre[i]);74 else printf(" %d",pre[i]);75 }76 printf("\n");77 }78 return 0;79 }