题目链接：http://poj.org/problem?id=2828
题意就是给你n个人，然后每个人按顺序插队，问你最终的顺序是怎么样的。
反过来做就很容易了，从最后一个人开始推，最后一个人位置很容易就确定了，那最后第二个人的位置也可以推(与最后一个人的位置无关)...依次就都可以确定所有的人了。
用前缀和的思想，要是这个人的位置确定了，那么就标记这个人位置的值为0，然后回溯更新，跟求逆序对个数的思想比较类似。
线段树：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + ;
struct segtree {
int l , r , val;
}T[MAXN << ];
int x[MAXN] , y[MAXN] , ans[MAXN] , id; void init(int p , int l , int r) {
T[p].l = l , T[p].r = r;
int mid = (l + r) >> ;
if(l == r) {
T[p].val = ;
return ;
}
init(p << , l , mid);
init((p << )| , mid + , r);
T[p].val = T[p << ].val + T[(p << )|].val;
} void updata(int p , int num) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == T[p].r) {
T[p].val = ;
id = T[p].l;
return ;
}
if(num <= T[p << ].val) {
updata(p << , num);
}
else {
updata((p << )| , num - T[p << ].val);
}
T[p].val = T[p << ].val + T[(p << )|].val;
} int main()
{
int n;
while(~scanf("%d" , &n)) {
init( , , n);
for(int i = ; i < n ; i++) {
scanf("%d %d" , x + i , y + i);
x[i]++;
}
for(int i = n - ; i >= ; i--) {
updata( , x[i]);
ans[id] = y[i];
}
for(int i = ; i < n ; i++) {
printf("%d " , ans[i]);
}
printf("%d\n" , ans[n]);
}
}
树状数组+二分：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + ;
int bit[MAXN] , n , x[MAXN] , y[MAXN] , ans[MAXN]; inline void add(int i , int num) {
for( ; i <= n ; i += (i & -i)) {
bit[i] += num;
}
} int sum(int i) {
int s = ;
for( ; i > ; i -= (i & -i))
s += bit[i];
return s;
} int main()
{
while(~scanf("%d" , &n)) {
memset(bit , , sizeof(bit));
for(int i = ; i <= n ; i++) {
scanf("%d %d" , x + i , y + i);
x[i]++;
add(i , );
}
for(int i = n ; i >= ; i--) {
int l = , r = n , mid;
while(l < r) {
mid = (l + r) >> ;
if(sum(mid) >= x[i])
r = mid;
else
l = mid + ;
}
ans[l] = y[i];
add(l , -);
}
for(int i = ; i < n ; i++) {
printf("%d " , ans[i]);
}
printf("%d\n" , ans[n]);
}
}