题意 : 有一块 h * w 的公告板，现在往上面贴 n 张长恒为 1 宽为 wi 的公告，每次贴的地方都是尽量靠左靠上，问你每一张公告将被贴在1~h的哪一行？按照输入顺序给出。
分析 : 这道题说明了每一次贴都尽量选择靠上靠左的位置，那既然这样，我们以1~h建立线段树，给每一个叶子节点赋值初值 w 表示当前行最大能够容纳宽度为 w 的公告纸，那么对于某一输入 wi 只要在线段树的尽量靠左的区间找出能够容纳这张公告的位置（即叶子节点）然后减去 wi 即可，需要对query()函数进行一点改造，将其返回的是叶子节点，判断递归的条件也由当前的 wi 决定。
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
;
];
int h, w, n;
] , maxv[rt<<|]); }
void build(int l,int r,int rt) {
maxv[rt] = w;
if (l == r) return ;
);
build(lson);
build(rson);
}
void update(int p,int sc,int l,int r,int rt) {
if (l == r) {
maxv[rt] += sc;
return ;
}
);
if (p <= m) update(p , sc , lson);
else update(p , sc , rson);
PushUP(rt);
}
int val;
int query(int l,int r,int rt) {
if(l == r) return l;
;
;
] >= val) ret = query(lson);///先判断左孩子，使得贴的位置会尽量靠上
else ret = query(rson);
return ret;
}
int main(void)
{
while(~scanf("%d %d %d", &h, &w, &n)){
if(h > n) h = n;///这里需要注意 h 最大是 1e9，但是很明显公告占行数最大只会到 n 这么大
build(, h, );///建树，一开始每一个节点的最大值都是 w
; i<=n; i++){
scanf("%d", &val);///输入每张公告的长度
] < val) puts("-1");///如果总区间中含有的最大空间都无法容纳当前公告，输出 -1
else{
, h, );///查找最大值的位置，注意返回的是位置
update(pos, -val, , h, );///将这个位置减去 wi
printf("%d\n", pos);///输出对应的位置
}
}
}
;
}
瞎 : 这道题要求返回的不是最大值，而是最大值的位置，如果硬套线段树模版肯定是不行的，需要对模版有很清楚的认识，不然很多变形题目就能难倒自己！