POJ 2828-Buy Tickets

约定不等于承诺〃 2022-09-24 06:16 102阅读 0赞

POJ 2828 线段树

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson rt<<1
#define rson (rt<<1)+1
using namespace std;
int s[200001<<2];
int a[200001],b[200001],c[200001];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        s[rt]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,lson);
    build(mid+1,r,rson);
    s[rt]=s[lson]+s[rson];
}
int query(int l,int r,int rt,int x)
{
    int t;
    if(l==r)
    {
        s[rt]=0;
        return l;
    }
    int mid=(l+r)>>1;
    if(s[lson]>=x)
        t=query(l,mid,lson,x);
    else
        t=query(mid+1,r,rson,x-s[lson]);
    s[rt]=s[lson]+s[rson];
    return t;
}
int main()
{
    int i,j,k,n,m,l;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            scanf("%d %d",&a[i],&b[i]);
        }
        build(1,n,1);
        for(i=n-1;i>=0;i--)
        {
            int t=query(1,n,1,a[i]+1);
         // printf("(%d)\n",t);
            c[t]=b[i];
        }
        for(i=1;i<=n;i++)
        {
            printf("%d ",c[i]);
        }
        printf("\n");
    }
    return 0;
}