HDU-2795

在学校的入口处有一个巨大的矩形广告牌，高为 $h$，宽为 $w$ 。所有种类的广告都可以贴，比如 ACM 的广告啊，还有餐厅新出了哪些好吃的，等等。。

在9月1号这天，广告牌是空的，之后广告会被一条一条的依次贴上去。

每张广告都是高度为 $1$ 宽度为 $w_i$ 的细长的矩形纸条。

贴广告的人总是会优先选择最上面的位置来帖，而且在所有最上面的可能位置中，他会选择最左面的位置，而且不能把已经贴好的广告盖住。

如果没有合适的位置了，那么这张广告就不会被贴了。

现在已知广告牌的尺寸和每张广告的尺寸，求每张广告被贴在的行编号。

思路

判断一个长为 $l$ 的矩形纸条是否能贴在第 $i$ 行，只需判断第 $i$ 行已经贴过的长度加上 $l$ 是否超过 $w$ 。

于是对于长为 $l$ 的矩形纸条，考虑如何查找到第一个能贴的行。

于是很自然的想到用线段树维护区间最小值，区间最小值用来判断该区间的行数能否贴下纸条。

查找到第一个能贴的行后对该行进行修改即可。

即用线段树维护区间最小值+单点修改

注意的是线段树的范围应取 $h$ 与 $n$ 之间的较小者（因为每个只占一行，且取满 $h$ 的话，空间无法承受）。

代码

#include<bits/stdc++.h>
#define N 200010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int h,w,n;
class SegmentTree{
  private:
    int minn[N<<2];
    #define m(x) minn[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        m(p)=min(m(ls),m(rs));
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            m(p)=0;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int x,int y) {
        if(l>x||r<x) return ;
        if(l==r) {
            m(p)+=y;
            return ;
        }
        modify(ls,l,mid,x,y),modify(rs,mid+1,r,x,y);
        update(p);
    }
    int ask(int p,int l,int r,int x) {
        if(m(p)+x>w) return -1;
        if(m(p)+x<=w&&l==r) return l;
        if(m(ls)+x<=w) return ask(ls,l,mid,x);
        if(m(rs)+x<=w) return ask(rs,mid+1,r,x);
    }
}SMT;

int main() {
    while(cin>>h>>w>>n) {
        int t=min(h,n);
        SMT.build(1,1,t);
        for(int i=1;i<=n;i++) {
            int x=read(),pos;
            pos=SMT.ask(1,1,t,x);
            printf("%d\n",pos);
            SMT.modify(1,1,t,pos,x);
        }
    }

    return 0;
}