POJ - 2828 线段树（插队问题）

题意：

每个人选择一个位置进入队列，后来的人会插到先来的人前面，问最后队伍上每个人的编号是多少。

思路：

插队问题，线段树单点更新，后来的人更有主动权，所以只要倒着考虑即可。然后每次插入到当前队列的第p[i]个空位上，sum[i]表示前i个位置中还有多少个空位。

代码：

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 const int MAXN = 2e5 + 10; int p[MAXN], v[MAXN], ans[MAXN]; struct SegmentTree { int sum[MAXN << 2]; void push_up(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void build(int l, int r, int rt) { if (l == r) { sum[rt] = 1; return; } int m = (l + r) >> 1; build(lson); build(rson); push_up(rt); } void update(int pos, int val, int l, int r, int rt) { if (l == r) { sum[rt] = 0; ans[l] = val; return; } int m = (l + r) >> 1; if (sum[rt << 1] >= pos) update(pos, val, lson); else update(pos - sum[rt << 1], val, rson); push_up(rt); } }segtree; int main() { int n; while (scanf("%d", &n) != EOF) { segtree.build(1, n, 1); for (int i = 1; i <= n; i++) { scanf("%d%d", &p[i], &v[i]); } for (int i = n; i >= 1; i--) { segtree.update(p[i] + 1, v[i], 1, n, 1); } for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' '); } return 0; }