pku2795 Billboard

#include<stdio.h>

const int MAX=200000;
struct Node
{
    int row,remainder;
};
Node tree[MAX*3];
Node error;
int h,w,n;

void build(int node,int l,int r)
{
    tree[node].remainder=w;    //每个树叶记录该行所剩余的空闲空间，树枝记录其树叶当中剩余空间最大的，若树叶的剩余空间相同，则记录行数最早出现的

    tree[node].row=l;

    if(l==r) return;
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
}

        //查询return第一个有足够剩余的树叶，而不是树枝，即使树枝记录其树叶的最大剩余空间，但其也只是表明一个存在性，不能通过树枝上记录行号而直接return该行号，必须搜索到树叶

Node inquire(int node,int l,int r,int space)
{
    if(tree[node].remainder<space)    return error;
    if(l==r) return tree[node];
    int mid=(l+r)/2;
    Node temp=inquire(node*2,l,mid,space);    //满足第一个判断表明存在该结点的树叶满足给定的空间要求，首先查找左子树，若左子树没有满足条件的树叶则在第一个条件处中断

    if(temp.row==-1) temp=inquire(node*2+1,mid+1,r,space); //若左子树找到了树叶，那么右子树即使有合适的树叶其行数肯定也比左子树的树叶的行数大，否则搜索右子树的树叶

    return temp;
}
                                        
void update(int node,int l,int r,int pos,int delta)    
{
    if(r==pos&&l==pos)                                //更新被占据空间的那一行的剩余空间

    {
        tree[node].remainder-=delta;
        return ;
    }

    int mid=(l+r)/2;
    if(pos<=mid) update(node*2,l,mid,pos,delta);
    else update(node*2+1,mid+1,r,pos,delta);

                                                    //自下而上的更新树枝，首先得搜索到树叶

    if(tree[node*2].remainder>tree[node*2+1].remainder) tree[node]=tree[node*2];    
    else if(tree[node*2].remainder<tree[node*2+1].remainder) tree[node]=tree[node*2+1];
    else tree[node]=tree[node*2].row>tree[node*2+1].row?tree[node*2+1]:tree[node*2];
}

int main()
{    
    error.row=-1;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        int length=h>n?n:h;    //length表示真正涉及到的行数


        build(1,1,length);
        while(n--)
        {
            int x;
            scanf("%d",&x);
            Node temp=inquire(1,1,length,x);
            printf("%d\n",temp.row);
            if(temp.row!=-1) update(1,1,length,temp.row,x);     //找到了合适的剩余空间就要更新那一行的剩余空间

        }
    }
    return 0;
}