POJ_2828

    这个题目和POJ_2182很像，我们可以从后往前依次查询，排在p的右边就说明自己是排在第p+1位的，因此，我们可以维护一个线段树，节点值表示当前区间内还有多少个位置，寻找到当前第p+1个位置的所在地时，就把value存进去，然后把这个位置删除，即自底向上更新一遍节点值即可。

#include
     
       #include
      
        #define MAXD 200010 int tree[4 * MAXD], q[MAXD], a[MAXD], b[MAXD], N, M; void init() {
   int i, j; for(M = 1; M < N + 2; M <<= 1);     memset(tree, 0, sizeof(tree)); for(i = 0, j = M + 1; i < N; i ++, j ++)         tree[j] = 1; for(i = M - 1; i; i --)         tree[i] = tree[2 * i] + tree[2 * i ^ 1]; for(i = 0; i < N; i ++)         scanf("%d%d", &a[i], &b[i]); } void solve() {
   int i, j, k; for(i = N - 1; i >= 0; i --)     {
           k = a[i] + 1; for(j = 1; j < M;)         {
   if(tree[2 * j] >= k)                 j <<= 1; else             {
                   k -= tree[2 * j];                 j = (j << 1) + 1;             }         }         q[j - M - 1] = b[i]; for(; j ^ 1; j >>= 1)             tree[j] --;     } for(i = 0; i < N; i ++)     {
   if(i)             printf(" ");         printf("%d", q[i]);     }     printf("\n"); } int main() {
   while(scanf("%d", &N) == 1)     {
           init();         solve();     } return 0; }