poj 2828 Buy Tickets 夜

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

坑爹呀你

c++ 跑不到2000

g++ 直接超时

有这么夸张吗 无语了

题目大意：

买票 不过有插队的 n个人依次插队

给你插队位置和value 问你最后value顺序

其实就是最后人的顺序

这题最好倒着插入因为 最后一个人如果插在第m个空的后面 那么他一定在m+1的位置

倒着来的话 无路第几个人 他插在第m个空的后面 那么他的左面就需要m个空位

在这里线段树只不过用来二分搜索

代码及其注释：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
const int N=200005;
struct node
{
    int empsum;
    int l,r;
}mem[N*4];
int pos[N];
int value[N];
int ans[N];
int n;
void build(int x,int l,int r)
{
    mem[x].l=l;
    mem[x].r=r;
    mem[x].empsum=(r-l+1);//初始这段空间的空格数
    if(l==r)
    return;
    int mid=(l+r)>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
}
void insert(int x,int i)
{
    --mem[x].empsum;//所到区间空位均减一
    if(mem[x].l==mem[x].r)
    {
        ans[mem[x].l]=value[i];//如果到了叶子节点 说明value的位置已找到
    }
    else
    {
        if(mem[x*2].empsum>pos[i])//如果左面有足够的空位则向左搜
        {
            insert(x*2,i);
        }
        else
        {
            pos[i]-=mem[x*2].empsum;//否则向右搜 不过在右面的话 所需空位置减少了左面的空位数
            insert(x*2+1,i);
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        build(1,1,n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d %d",&pos[i],&value[i]);
        }
        for(int i=n;i>=1;--i)
        {
            insert(1,i);
        }
        for(int i=1;i<=n;++i)
        {
            if(i>1)
            printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}