POJ 2828 Buy Tickets(线段树单点)

https://vjudge.net/problem/POJ-2828

题目意思：有n个数，进行n次操作，每次操作有两个数pos, ans。pos的意思是把ans放到第pos 位置的后面，pos后面的数就往后推一位。最后输出每个位置的ans。

    思路：根据题 目可知，最后插入的位置的数才是最终不变的数，所以可以从最后的输入作第1个放入，依此类推，倒插入。在插入时也有一定的技术，首先创建一棵空线段树时，每个节点记录当前范围内有多少个空位置。在插入时，要注意，一个数放入之后那么这个位置就不用管了，那么树中所有的空位置就是余下的数所对应的位置，也就是把余下的数又可以看作是一个新的集合。那么每次插入都是当前集合的第1次放。

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <deque>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <functional>
// #include <bits/stdc++.h>
using namespace std;

int n,ans[1000000];

struct node
{
    int n,val;
}a[1000000];

struct tree
{
    int l,r,n;
}b[1000000];

void init()
{
    int i,j,k;
    for(k=1;k<n;k<<=1);
    for(i=k;i<2*k;i++)
    {
        b[i].l=b[i].r=i-k+1;
        b[i].n=1;//每个叶子节点只能放入一个人
    }
    for(i=k-1;i>0;i--)
    {
        b[i].l=b[2*i].l;
        b[i].r=b[2*i+1].r;
        b[i].n=b[2*i].n+b[2*i+1].n;//每个区间是其左右子树所能放入的人数总和
    }
}

void insert(int i,int x,int m)
{
    if(b[i].l==b[i].r)//找到叶子节点，这个节点存放该人，并且叶子节点能放入的人数清0
    {
        ans[b[i].l]=m;
        b[i].n=0;
        return;
    }
    if(x<=b[2*i].n)//其插入的位置若能放入左子树（还能放人），往左子树放人，否则走右子树
        insert(2*i,x,m);
    else
        insert(2*i+1,x-b[2*i].n,m);
        b[i].n--;
}

int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&a[i].n,&a[i].val);
        init();
        for(i=n;i>0;i--)//逆推
        {
            insert(1,a[i].n+1,a[i].val);
        }
        cout<<ans[1];
        for(i=2;i<=n;i++)
            cout<<" "<<ans[i];
        cout<<endl;
    }
    return 0;
}