poj2828 라인 트리 단일 업데이트

1206 단어
#include<stdio.h>
#include<string.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max 200010
int sum[max<<2];
int ans[200010];
int tem1[200010];
int tem2[200010];
int n,t;
void build(int l,int r,int rt)
{
    sum[rt]=r-l+1;
    if(r==l)
       return ;
    int m=(r+l)>>1;
    build(lson);
    build(rson);
}
void update(int x,int l,int r,int rt)
{
    sum[rt]--;
    if(l==r)
    {
        t=l;
        return ;
    }
    int m=(l+r)>>1;
    if(sum[rt<<1]>=x)
      update(x,lson);
    else
    {
        x-=sum[rt<<1];
        update(x,rson);
    }
}
int main()
{
    int i;
    while(~scanf("%d",&n))
    {
        build(1,n,1);
        for(i=0;i<n;i++)
        {
           scanf("%d%d",&tem1[i],&tem2[i]);
        }
        for(i=n-1;i>=0;i--)
        {
           update(tem1[i]+1,1,n,1);
           ans[t]=tem2[i];
        }
        for(i=1;i<=n;i++)
        {
               if(i==1)
                printf("%d",ans[i]);
            else
                printf(" %d",ans[i]);
        }
      printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기