hdu2795 Billboard 线段树

题意：

给出一块h*w的广告牌，还有n张1*u的海报，海报尽量往上，左边的位置张贴，问每一张海报能贴的多高。

线段树单点修改。

注意：因为1 <= h,w <= 10^9; 1 <= n <= 200,000，但实际上，若h>n的话，最坏的情况下也只要用到前n行。

所以若h>n  则h=n

如果不加这一句，因为线段树的数组要开到h<<2这么大，又h<= 10^9，所以输入的h过大时会使开的数组过大。加了的话，就不会啦，n<<2是OK的。

#include<cstdio>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxh=200010;
int _max[maxh<<2];
int ans;
void pushup(int rt)
{
    _max[rt]=max(_max[rt<<1],_max[rt<<1|1]);
}
void query(int u,int l,int r,int rt)
{
    if(l==r){
        _max[rt]-=u;
        ans=l;
        return ;
    }
    int m=(l+r)>>1;
    if(_max[rt<<1]>=u)
        query(u,lson);
    else
        query(u,rson);
    pushup(rt);
}
int main()
{
    int h,w,n;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF){
        if(h>n)
            h=n;
        for(int i=1;i<=(h<<2);i++)
            _max[i]=w;
        int u;
        for(int i=0;i<n;i++){
            scanf("%d",&u);
            if(_max[1]<u)
                printf("-1
");
            else{
                query(u,1,h,1);
                printf("%d
",ans);
            }
        }
    }
    return 0;
}