[线段树]hdoj 2795

题意：一个高h宽w的二维空间，每次放进去一个高为1，宽为a的物体，每次存放物体都是优先放在最高的位置，其次优先放在最靠右的位置，对于每一次放入物品，输出这个物品放在第几行。

 

思路：用线段树，每个线段初始val为w，每次查询返回最高一行可以存放的位置，并且更新区间节点最大值val

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int nMax = 200020;
struct{
    int l,r,val;
}node[nMax*3];
int h,w;
void build(int l, int r, int u){
    node[u].val = w;
    node[u].l=l;
    node[u].r=r;
    if(l == r){
        return;
    }
    int m = (l+r)/2;
    build(l , m ,u*2);
    build(m+1 , r, u*2 + 1);
}

int update(int p,int u){
    int l = node[u].l;
    int r = node[u].r;
    if(l == r){
        if(node[u].val>=p){
            node[u].val -= p;
            return r;
        }else{
            return -1;
        }
    }
    int ans = -1;
    if(p<=node[2*u].val)ans = update(p,2*u);
    else if(p<=node[2*u+1].val)ans = update(p,2*u+1);
    node[u].val = max(node[2*u].val,node[2*u+1].val);
    return ans;
}

int main(){
    int n , a ;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF){
        build(1,min(h,n),1);
        while(n--){
            scanf("%d",&a);
            int loc = update(a , 1);
//            cout<<loc<<endl;
            printf("%d\n",loc);
        }
    }
    return 0;
}