POJ 2828 单点更新

题意：给出N个人要查入队伍中的位置，按照输入的顺序，求最后队伍的先后顺序。

先把输入存起来，从后往前插入，前一个序号就代表前面有几个人，线段树内记录当前位置是否被占了，找低Num+1个空位坐下就行，查询函数返回空总和为num+1的位置。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=200005;
int node[maxn<<2];
int yl[maxn][2],q[maxn];
void build(int l,int r,int rt)
{
    node[rt]=r-l+1;
    if(l==r)
        return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
int query(int pos,int l,int r,int rt)
{
    node[rt]--;
    if(l==r)
    {
        return l;
    }
    int m=(l+r)>>1;
    int ret=0;
    if(pos<=node[rt<<1])
        ret=query(pos,lson);
    else
        ret=query(pos-node[rt<<1],rson);
    return ret;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        build(1,n,1);
        for(int i=0; i<n; i++)
            scanf("%d%d",&yl[i][0],&yl[i][1]);
        for(int i=n-1; i>=0; i--)
            q[query(yl[i][0]+1,1,n,1)]=yl[i][1];
        for(int i=1; i<=n; i++)
            printf("%d%c",q[i],i!=n?' ':'\n');
    }
    return 0;
}