Buy Tickets---poj2828（线段树）

题目链接：http://poj.org/problem?id=2828

题意就是有n个x y每次都是把y放到x位置，如果x位置有数，则把该位置之后的数往后放一位；

【题解】：

　　　　线段树节点中保存这一段中的空位数，然后倒序对pos插入：

　　　　例如：　　0 77
　　　　　　　　　1 51
　　　　　　　　　1 33
　　　　　　　　　2 69

　　先取： 2 69　　 —— —— —69— —— （需要前面有3个空位才能插入）

然后取： 1 33 —— —33— —69— —— （需要前面有2个空位才能插入）

然后取： 1 51 —— —33— —69— —51— （需要前面有2个空位才能插入）前面只有1个空位故插入后面空格

　　然后取： 0 77 —77— —33— —69— —51— （需要前面有1个空位才能插入）

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 200010
#define Lson r<<1
#define Rson r<<1|1
using namespace std;

struct SegTree
{
    int L, R, sum;
    int mid()
    {
        return (L+R)/2;
    }
}a[4*N];

struct node
{
    int x, y;
}b[N];
int ans[N];
void BuildTree(int r, int L, int R)
{
    a[r].L = L;
    a[r].R = R;
    a[r].sum = R-L+1;
    if(L==R)
        return;
    BuildTree(Lson, L, a[r].mid());
    BuildTree(Rson, a[r].mid()+1, R);
}
int Update(int x, int r)
{
    a[r].sum--;
    if(a[r].L == a[r].R)
        return a[r].L;///返回插入位置;
    if(a[Lson].sum >= x)
        return Update(x, Lson);
    else
    {
        x-=a[Lson].sum;///当左边的空格小于x，则插入右边，插入右边位置x应该减左边的空格数
        return Update(x, Rson);
    }
}
int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=0; i<n; i++)
            scanf("%d%d", &b[i].x, &b[i].y);
        BuildTree(1, 1, n);
        for(int i=n-1; i>=0; i--)
        {
            int id = Update(b[i].x+1, 1);
            ans[id] = b[i].y;
        }
        for(int i=1; i<n; i++)
            printf("%d ", ans[i]);
        printf("%d
", ans[n]);
    }
    return 0;
}

View Code