解题思路

这道题目要求我们模拟一个动态插队的过程，并最终输出队列中每个人的值。关键在于如何高效地处理多次插入操作，使得最终队列的顺序正确。

关键观察

1. 逆序处理：如果我们正序处理每次插入（即按照输入顺序依次插入），每次插入会影响后续的位置计算，导致时间复杂度较高（最坏情况下是$O(N^2)$）。因此，可以采用逆序处理的方式，即从最后一个人开始往前插入。这样，每次插入的位置不会影响之前已经处理好的部分。

2. 线段树维护剩余空位：为了高效地找到第$k$个空位（即第$k$个可插入的位置），可以使用线段树来维护当前剩余的空位数。线段树的每个节点存储区间$[l, r]$内的剩余空位数，这样可以在$O(\log N)$的时间内找到目标位置。

算法步骤

1. 初始化线段树：建树时，每个叶子节点初始化为$1$（表示该位置为空），父节点存储子节点的空位数之和。
2. 逆序处理插入操作：
   • 对于第$i$个人（从后往前处理），他要插入的位置是$Pos_i + 1$（因为$Pos_i$表示插在第$Pos_i$个人后面）。
   • 在线段树中查询第$Pos_i + 1$个空位的位置，并将该位置标记为已占用（更新线段树）。
   • 将该人的值$Val_i$存入答案数组的对应位置。
3. 输出最终队列：所有插入操作完成后，答案数组即为最终的队列顺序。

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 2e5 + 7;

int n, ans[maxN], a[maxN], val[maxN];

struct Tree{
    int l, r, sum;
}t[maxN << 2];

void build(int l, int r, int num)
{
    t[num].l = l; t[num].r = r;
    if(l == r) {
        t[num].sum = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, num << 1);
    build(mid + 1, r, num << 1 | 1);
    t[num].sum = t[num << 1].sum + t[num << 1 | 1].sum;
}

void change(int num, int pos, int x, int val) // 寻找第x个空余位置，并修改，然后记录答案
{
    if(t[num].l == t[num].r) {
        t[num].sum += x;
        ans[t[num].l] = val;
        return ;
    }
    int mid = (t[num].l + t[num].r) >> 1;
    if(pos <= t[num << 1].sum)
        change(num << 1, pos, x, val);
    else 
        change(num << 1 | 1, pos - t[num << 1].sum, x, val);
    t[num].sum = t[num << 1].sum + t[num << 1 | 1].sum;
}

int main()
{
    while(~scanf("%d", &n)) {
        build(1, n, 1);
        for(int i = 1; i <= n; ++i) 
            scanf("%d%d", &a[i], &val[i]);
        for(int i = n; i >= 1; --i)
            change(1, a[i] + 1, -1, val[i]);
        for(int i = 1; i <= n; ++i)
            printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}