题目传送门 http://poj.org/problem?id=2828

题目大意：每次插队的时候插到第$POs[i]$个人后面去，最后打印出最终的排列，(好暴力的插队方式啊~~

在中国都很少见呢~ ><

题目思路：从后面往前遍历，一个一个将那个人插到还有的第$POS[i] + 1$个空格那里，神奇的思路，在线段树上每个节点有如下变量

$num\quad$用于维护该区间还剩下的空格数

$value\quad$用于记录该点的value值，和题意相同，不过这个变量只用于线段树的叶子

$id\quad$用于维护原序列

第一次写线段树只看了思路然后就AC的，完全没参考别人的代码…….看来我对线段树的了解上了一个层次了233， $$But\quad Still \quad Long\quad Long\quad Wait\quad To\quad Go!!$$%

#include <cstdio>#include <algorithm>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define ll rt<<1#define rr rt<<1|1const int maxn = 222222;struct node{    int id,value,num;};int n;node get[maxn];node sum[maxn<<2];void PushUp(int rt) {    sum[rt].num = sum[ll].num + sum[rr].num;}void build(int l,int r,int rt) {    if(l == r) {        sum[rt].num = 1;        sum[rt].id = 0;        sum[rt].value = http://www.mamicode.com/0;"%d\n",get[sum[rt].id].value);        return ;    }else if(l == r) {        printf("%d ",get[sum[rt].id].value);        ans_num++;        return ;    }    int m = (l + r) >> 1;    print(lson);    print(rson);}int main() {    while(~scanf("%d",&n)) {        for(int i = 1;i <= n;++i) {            scanf("%d%d",&get[i].num,&get[i].value);            get[i].id = i;        }        build(1,n,1);        //printf("%d\n",sum[1].num);        for(int i = n;i >= 1;--i) {            update(i,get[i].num+1,get[i].value,1,n,1);        }        ans_num = 1;        print(1,n,1);    }    return 0;}

POJ 2828