HDU2795–Billboard(单点修改&&区间最值）

题目大意

给定一个大小为h*w的矩形和n个子矩阵，大小分别为1*w₁,1*w₂,1*w₃,..1*w_n。要求你把n个子矩阵按给出顺序依次放置在大矩阵中(如果能够放入的话），使得放置的位置尽量靠顶端，如果有几种情况符合条件的话，选择最靠左的位置放置，要求你输出每个子矩阵放置的位置的行数，如果不能能放置则输出-1

题解

线段树的单点修改和区间最值问题，把每一行作为线段树的一个叶子结点，每个叶子结点的初始值都为w。在进行查询的时候，如果左边的最大值大于等于子矩阵的大小就对左子树进行递归查询，否则的话只能在右子树进行查询，找到符合要求的叶子结点，对其进行修改并返回它的行数

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define lson l, m , s << 1
#define rson m + 1 , r , s << 1 | 1
#define MAXN 200005
using namespace std;
int w;
int maxv[MAXN<<2];
void PushUP(int s)
{
    maxv[s] = max(maxv[s<<1] , maxv[s<<1|1]);
}
void build(int l,int r,int s)
{
    if(l==r)
    {
        maxv[s]=w;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUP(s);
}
int query(int p,int l,int r,int s)
{
    if(l==r)
    {
        maxv[s]-=p;
        return l;
    }
    int m=(l+r)>>1,ans;
    if(maxv[s<<1]>=p)
    ans=query(p,lson);
    else
    ans=query(p,rson);
    PushUP(s);
    return ans;
}
int main(void)
{
    int h,n,k,i;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        if(h>n) h=n;
        build(1,h,1);
        for(i=1; i<=n; i++)
        {
            scanf("%d",&k);
            if(k>maxv[1])
                printf("-1\n");
            else
                printf("%d\n",query(k,1,h,1));
        }
    }
    return 0;
}