題目鏈接：http://poj.org/problem?id=2828
/**//*
題意：
給定N(1 <= N <= 200000)個(gè)整數(shù)對(duì)(A,B)，表示在A右邊的位置插入一個(gè)B，
經(jīng)過(guò)N次操作后問(wèn)最后的B序列的排列情況。
題解：
樹(shù)狀數(shù)組 或者 線段樹(shù)
思路：
這題的數(shù)據(jù)量比較大，一開(kāi)始可以模擬一下過(guò)程，但是直接暴力肯定是超時(shí)
的，因?yàn)槊看尾迦脒^(guò)程，這個(gè)位置的后面的元素必然是要順序往后移動(dòng)的。所以
總的復(fù)雜度高達(dá)O(n^2)。
但是這個(gè)問(wèn)題可以轉(zhuǎn)化，我們這樣考慮，對(duì)于任意兩個(gè)整數(shù)對(duì)(A1,B1)和(A2,B2)
保證(A1,B1)在(A2,B2)之前出現(xiàn)，如果A1小于A2，后面的整數(shù)對(duì)是不影響前面整
數(shù)對(duì)的位置關(guān)系的，否則B1的位置必然要受到B2的影響而向后移動(dòng)一位。
于是A1和A2之間就存在一個(gè)逆序關(guān)系，我們可以聯(lián)想到樹(shù)狀數(shù)組求逆序數(shù)時(shí)
候的做法，從后往前，對(duì)于最后一個(gè)數(shù)，它的位置就是An，因?yàn)橹鬀](méi)有插入數(shù)
了，它已經(jīng)穩(wěn)定下來(lái)了，然后將這個(gè)位置插入到樹(shù)狀數(shù)組的相應(yīng)位置去，每次掃
描到當(dāng)前數(shù)的時(shí)候二分枚舉當(dāng)前數(shù)前面有多少“空位”，空位的統(tǒng)計(jì)可以采用樹(shù)
狀數(shù)組的成段求和，找到后將這個(gè)數(shù)插入，N次操作后答案就保存下來(lái)了。
*/
#include <iostream>
using namespace std;
#define maxn 200010
int n;
int c[maxn];
struct point 
{
int A, B;
}pt[maxn];
int lowbit(int x) {
return x & (-x);
}
void add(int pos) {
while(pos <= n) {
c[pos] ++;
pos += lowbit(pos);
}
}
int sum(int pos) {
int s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
int ans[maxn];
int main() {
int i;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++)
c[i] = 0;
for(i = 1; i <= n; i++) {
scanf("%d %d", &pt[i].A, &pt[i].B);
pt[i].A ++;
}
for(i = n; i >= 1; i--) {
int l = 1;
int r = n;
int as = 1;
while(l <= r) {
int m = (l + r) >> 1;
if(m - sum(m) >= pt[i].A) {
r = m - 1;
as = m;
}else
l = m + 1;
}
ans[as] = pt[i].B;
add(as);
}
for(i = 1; i <= n; i++) {
if(i != 1)
printf(" ");
printf("%d", ans[i]);
}
puts("");
}
return 0;
}