POJ2828 Buy Tickets

题目大意

有n个陆续去售票口排队买票，每个人都会插队，第i个人会插到位置为pos[i]的人的后面，问最后队列的情况

题解

我们可以发现，对于第n个人，它插入的位置就是他最终站的位置，因此我们从第n个人开始处理，对于第i个人，找到第pos[i]+1个空位插入即可，然后空位减少一个，查找空位和对空位数量进行修改刚好可以用线段树来处理

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define lson l, m , s << 1
#define rson m + 1 , r , s << 1 | 1
#define MAXN 200005
using namespace std;
int val[MAXN<<2],pos[MAXN<<2],sumv[MAXN<<2],ans[MAXN],t;
void build(int l,int r,int s)
{
    sumv[s]=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 s)
{
    sumv[s]--;
    if(l==r)
    {
        t=l;
        return;
    }
    int m=(l+r)>>1;
    if(p<=sumv[s<<1]) update(p,lson);
    else update(p-sumv[s<<1],rson);
}
int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        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);
            ans[t]=val[i];
        }
        for(int i=1; i<n; i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}