POJ-2828-Buy Tickets

線段樹，逆序插入

[cpp]
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
using namespace std; 
#define N 200010 
struct cam 
{ 
    int x,y; 
    int num; 
}list[N*8]; 
int pos[N],value[N],ans[N]; 
int n; 
void build(int k,int x,int y)  //用線段樹存儲區間內還有多少位子沒有被占 
{ 
    list[k].x=x; 
    list[k].y=y; 
    list[k].num=(y-x+1); 
    if(x==y) 
    return; 
    int mid; 
    mid=(x+y)/2; 
    build(k<<1,x,mid); 
    build(k<<1|1,mid+1,y); 
} 
void find(int k,int pos,int value) 
{ 
    list[k].num--; 
    if(list[k].x==list[k].y) 
    { 
        ans[list[k].x]=value; 
        return; 
    } 
    if(list[k<<1].num>=pos) 
    find(k<<1,pos,value); 
    else 
    find(k<<1|1,pos-list[k<<1].num,value); 
} 
int main() 
{ 
    int i; 
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=1;i<=n;i++) 
        scanf("%d%d",&pos[i],&value[i]); 
        build(1,1,n); 
        for(i=n;i>=1;i--) 
        find(1,pos[i]+1,value[i]); 
        for(i=1;i<=n;i++) 
        { www.2cto.com
            if(i==n) 
            printf("%d\n",ans[i]); 
            else 
            printf("%d ",ans[i]); 
        } 
    } 
    return 0; 
}