poj 2828(线段树 逆向思考) 插队是不好的行为

http://poj.org/problem?id=2828

插队问题,n个人,下面n行每行a,b表示这个人插在第a个人的后面和这个人的编号为b,最后输出队伍的情况

涉及到节点的问题可以用到线段树,这里因为每个人插队时有顺序的,如果按照正着的顺序来情况太复杂,所以可以试试倒过来,从最后一个人开始,此时找到的位置

一定是最终位置,这样就很简单了,   结构体中多开一个mark表示每个区间的空位置,多开一个sum表示人的编号

这道题不错,提醒我们有时候换一换思路,逆向思考一下

 #include<cstdio>

 using namespace std;

 struct point {

     int l,r;

     int sum,mark;

 };

 point tree[*];

 int a[],b[];

 void build(int i,int left,int right)

 {

     tree[i].l=left,tree[i].r=right;

     tree[i].mark=(tree[i].r-tree[i].l)+;

     tree[i].sum=;

     if (right==left) return;

     int mid=(left+right)/;

     build(i*,left,mid);

     build(i*+,mid+,right);

 }

 void update(int i,int pos,int val)

 {

     if (tree[i].l==tree[i].r)

     {

         tree[i].sum=val;

         tree[i].mark--;

         return ;

     }

     if (pos<=tree[i*].mark)

        update(i*,pos,val);

     else

        update(i*+,pos-tree[i*].mark,val);

     tree[i].mark=tree[i*].mark+tree[i*+].mark; //更新区间的空位

 }

 void check(int i)

 {

     if (tree[i].l==tree[i].r)

     {

        printf("%d ",tree[i].sum);

        return ;

     }

     check(i*);

     check(i*+);

 }

 int main()

 {

     int n,i;

     while (~scanf("%d",&n))

     {

         for (i=;i<=n;i++)

            scanf("%d %d",&a[i],&b[i]);

        build(,,n);

        for (i=n;i>;i--)

            update(,a[i]+,b[i]);

        check();

        printf("\n");

     }

     return ;

 }