插入队列进行逆向操作,pos代表的也就是放入此人时前面应有pos个空位,用线段树维护空位数量。
/****************************************************/ #include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <cctype> #include <stack> #include <map> #include <queue> #include <algorithm> #include <ctime> #define EPS 1E-8 #define MAXN 200010 #define INF (~0U >> 2) #define MOD 1000000007 #define Lson l, mid, rt << 1 #define Rson mid + 1, r, rt << 1 | 1 using namespace std; typedef long long LL; /****************************************************/ int num[MAXN << 2], res[MAXN], p; struct P { int val, pos; }a[MAXN]; void push_up(int rt) { num[rt] = num[rt << 1] + num[rt << 1 | 1]; } void build(int l, int r, int rt) { if (l == r) { num[rt] = 1; return; } int mid = (l + r) >> 1; build(Lson); build(Rson); push_up(rt); } void query(int x, int l, int r, int rt) { if (l == r) { //puts("ok"); p = l; //cout << p << endl; num[rt] = 0; return; } int mid = (l + r) >> 1; if (num[rt << 1] > x) query(x, Lson); else query(x - num[rt << 1], Rson); push_up(rt); } int main() { int N; while (scanf("%d", &N) != EOF) { build(1, N, 1); for (int i = 0; i < N; i++) { scanf("%d%d", &a[i].pos, &a[i].val); } for (int i = N - 1; i >= 0; i--) { int x = a[i].pos; query(x, 1, N, 1); res[p] = a[i].val; } printf("%d", res[1]); for (int i = 2; i <= N; i++) printf(" %d", res[i]); puts(""); } }