算法竞赛进阶指南，261页， 树状数组，二分查找
题目意思：
有 n 个人，每个人有一个权值，初始队列没有人，这 n 个人进行 n 次插队，每次插队代表一个权值为 val 的人插入第 x 个位置后。
最后从前往后输出每个人的权值。 题目类似于 POJ 2182
本题要点：
1、 虽然一个人现在插在 x 位置后，但是它最终的位置不一定是 x+1 ，再后来人的插入后可能位置还会变。
但是，最后一个人插在 x 位置，这个人最后就是在 x+1 位置上；倒数第二个人，只用将最后一个人的位置"留空"，
再找第 x 个没有"留空"的位置插入即可。
2、 初始化一个数组b， 每个位置要么是0，要么是1; 用树状数组来维护数组b，
然后从后往前扫描数组a：
1）寻找数组b中第 p[i].pos 个1的下标 idx， 这个下标就是第i人的排队的位置
2）将数组b的第 idx 个1置零。实际就是 树状数组 update(idx, -1);
3、 用二分查找来寻找数组b中第 p[i].pos 个1的下标
#include <cstdio>
#include <cstring>
#include <iostream>
#define lowbit(i) ((i)&(-i))
using namespace std;
const int MaxN = 200010;
int a[MaxN];
//int b[MaxN]; //计算逻辑上的b数组，存放的是 01 序列
int c[MaxN];
int ans[MaxN];
int n;struct Person
{
int pos, val;
}p[MaxN];int getSum(int k)
{
int res = 0;while(k){
res += c[k];k ^= lowbit(k); //这里使用 异或来代替 k -= lowbit(k), 计算速度快一点}return res;
}void update(int x, int v)
{
for(int i = x; i <= n; i += lowbit(i)){
c[i] += v; }
}bool judge(int mid, int s)
{
return getSum(mid) >= s;
}int find_index(int s)
{
int L = 1, R = n + 1, mid;while(L < R){
mid = (L + R) / 2; if(judge(mid, s)){
R = mid;}else{
L = mid + 1;}}return L;
}void solve()
{
memset(c, 0, (n + 1) * sizeof(int));for(int i = 1; i <= n; ++i){
update(i, 1); }int idx;for(int i = n; i >= 1; --i){
idx = find_index(p[i].pos);ans[idx] = p[i].val; update(idx, -1);}for(int i = 1; i < n; ++i){
printf("%d ", ans[i]);}printf("%d\n", ans[n]);
}int main()
{
while(scanf("%d", &n) != EOF){
for(int i = 1; i <= n; ++i){
scanf("%d%d", &p[i].pos, &p[i].val);p[i].pos++;}solve();}return 0;
}/* 4 0 77 1 51 1 33 2 69 4 0 20523 1 19243 1 3890 0 31492 *//* 77 33 69 51 31492 20523 3890 19243 */