线段树(单点更新) POJ 2828 Buy tickets

题目传送门

/*
    结点存储下面有几个空位
    每次从根结点往下找找到该插入的位置，
    同时更新每个节点的值
*/
#include <cstdio>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1

const int MAX_N = 200000 + 10;
int pos[MAX_N], val[MAX_N];
int sum[MAX_N << 2];
int que[MAX_N];
int id;

void build(int l, int r, int rt)
{
    sum[rt] = r - l + 1;        //节点有多少个空位置
    if (l == r)        return ;
    int m = (l + r) >> 1;
    build (lson);
    build (rson);
}

void update(int p, int l, int r, int rt)
{
    sum[rt]--;                    //插入一个减少一个空位置
    if (l == r)                    //找到了传递该位置
    {
        id = l;
        return ;
    }
    int m = (l + r) >> 1;
    if (p <= sum[rt<<1])
    {
        update (p, lson);
    }
    else
    {
        p -= sum[rt<<1];    //减去
        update (p, rson);
    }
}

int main(void)        //POJ 2828 Buy tickets
{
    //freopen ("inE.txt", "r", stdin);
    int n;

    while (~scanf ("%d", &n))
    {
        build (1, n, 1);
        for (int i=1; i<=n; ++i)
        {
            scanf ("%d%d", &pos[i], &val[i]);
        }
        for (int i=n; i>=1; --i)        //最后插入的位置不变
        {
            update (pos[i]+1, 1, n, 1);
            que[id] = val[i];
        }
        printf ("%d", que[1]);
        for (int i=2; i<=n; ++i)
        {
            printf (" %d", que[i]);
        }
        puts ("");
    }

    return 0;
}