[线段树]poj 2828

题意

??????n个人插队，每次某个人都会选择插入第i个人背后，输出最终的排队序列。

思路

?????建立一颗线段树，节点val值为，这个区间的空位数，然后从后向前更新线段树，也就是说，如果一个节点无法插入当前位置，那么就选择右侧最靠近这个节点的位置

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 200010;
struct{
    int l,r,val;
}node[nMax*3];
void build(int l, int r,int u){
    node[u].l = l;
    node[u].r = r;
    node[u].val = r - l + 1;
    if(r == l)return;
    else{
        int m = (l + r) >> 1;
        build(l , m , u*2);
        build(m+1 , r , u*2 + 1);
    }

}

int id;
void update(int p ,int u){
    int l = node[u].l;
    int r = node[u].r;
    node[u].val -= 1;
    if(l == r){
        id = l;
        return;
    }
    if(p <= node[2*u].val){
        update(p , u*2);
    }else{
        update(p-node[2*u].val,u*2+1);
    }

}

int loc[nMax],val[nMax],ans[nMax];
int main(){
    int n,i;
    while(scanf("%d",&n)!=EOF){
        for(i=1 ; i <= n; i++){
            scanf("%d%d",&loc[i],&val[i]);
        }
        build(1, n, 1);
        for(i=n ; i >= 1 ; i--){
            update(loc[i]+1 , 1);
            ans[id] = val[i];
        }
        for(i = 1; i < n; i++){
            printf("%d ",ans[i]);
//            cout<<ans[i]<<" ";
        }printf("%d\n",ans[i]);
    }
    return 0;
}

?

[线段树]poj 2828

原文：http://bbezxcy.iteye.com/blog/2161055