HDUOJ 2795 Billboard（线段树）

题意：有一面hw的墙，有n个大小为 1wi宣传单，每次贴都从最左最上能贴的位置开始贴，求每一宣传单被贴在哪一行。
solution：线段树以1-h划分成区间，每个区间存放着该区间能放下的最大长度，每次从最上面开始找，找到符合的区间并更新

#include <bits/stdc++.h>
using namespace std;

struct node{
	int l, r, res;
}tree[8000001];
int ans[2000001], h, w;

void build(int root, int l, int r)
{
	tree[root].l = l;
	tree[root].r = r;
	tree[root].res = w;
	if (tree[root].l == tree[root].r)return;
	int mid = (r + l) / 2;
	build(root * 2, l, mid);
	build(root * 2 + 1, mid + 1, r);
}

int query(int root, int len)
{
	if (tree[root].l == tree[root].r){
		tree[root].res -= len;
		return tree[root].l;
	}
	int ret;
	if (tree[root * 2].res >= len)ret = query(root << 1, len);
	else ret = query(root << 1 | 1, len);
	tree[root].res = max(tree[root << 1].res, tree[root << 1 | 1].res);
	return ret;
}

int main()
{
	int len, n;
	while (cin >> h >> w >> n)
	{
		if (h > n)h = n;
		build(1, 1, h);
		while (n--)
		{
			scanf("%d", &len);
			if (len > tree[1].res)cout << -1 << endl;
			else cout << query(1, len) << endl;
		}
	}
	return 0;
}