HDU 2795 Billboard (线段树)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795

题目大意：有一块h*w的矩形广告板，要往上面贴广告;   然后给n个1*wi的广告，要求把广告贴上去； 而且要求广告要尽量往上贴并且尽量靠左;  求每个广告的所在的位置，不能贴则为-1。

用线段树模拟，要是左子树的最大值比当前广告大，就查询更新左子树，否则就右子树。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + 5;
struct segtree {
    int l , r , val;
}T[MAXN << 2];
int w , a[MAXN] , res;

void init(int p , int l , int r) {
    T[p].l = l , T[p].r = r;
    int mid = (l + r) >> 1;
    if(l == r) {
        T[p].val = w;
        return ;
    }
    init(p << 1 , l , mid);
    init((p << 1)|1 , mid + 1 , r);
    T[p].val = max(T[p << 1].val , T[(p << 1)|1].val);
}

void query(int p , int val) {
    if(T[p].l == T[p].r) {
        T[p].val -= val;
        res = T[p].l;
        return ;
    }
    if(val <= T[p << 1].val) {
        query(p << 1 , val);
    }
    else {
        query((p << 1)|1 , val);
    }
    T[p].val = max(T[p << 1].val , T[(p << 1)|1].val);
}

int main()
{
    int h , n;
    while(~scanf("%d %d %d" , &h , &w , &n)) {
        h = min(h , n);
        init(1 , 1 , h);
        for(int i = 0 ; i < n ; i++) {
            scanf("%d" , a + i);
            if(T[1].val < a[i])
                printf("-1
");
            else {
                query(1 , a[i]);
                printf("%d
" , res);
            }
        }
    }
}