hdu2795 线段树

     题意：有一块木板，木板的长和宽分别是h，w(1 <= h, w <= 10^9)，现在有n（1 <= n <= 200000）个公告要放在木板上面，规定：木板必须竟可能往上面放，如果同一行有多个可选位置，尽量往左放，如果没有位置放置该公告输出 ' -1',否则输出该公告放置的高度。

  分析：共有n个公告，最多放置n行，当h >= n时根本不可能会有公告放在上面，所有以高度的区间作为线段树节点，节点存储该高度区间内的宽度最大值，以及该宽度所在的高度：

struct node{	int h, w; //宽度最大的 position}t[maxn];初始时，每个区间的最大值就是木板的宽度，每次放入一个公告，找到其放置的高度，并更新所有包含该高度的区间的最大值即可。
查询时，应当向可能出现比当前高度h更小的高度的区间搜索。如果当前区间的最大宽度都无法插入公告，就退出搜索。
AC代码：
#include<cstdio>#include<algorithm>using namespace std;const int maxn = 8e5;const int inf = 1 << 30;struct node{	int h, w; //宽度最大的 position}t[maxn];struct point{ //担心内存撑不住，另开的数组	int l, r;}f[maxn];int H, W, N;void Build(int l, int r, int cur){ //建树 	f[cur].l = l, f[cur].r = r;	t[cur].h = l, t[cur].w = W;	if(l == r) return;	int mid = (l + r) / 2;	Build(l, mid , cur << 1);	Build(mid + 1, r, (cur << 1) + 1);}int search(int w, int h, int cur){  //搜索w应该放置的位置 	int h1 = t[cur].h, w1 = t[cur].w;	if(w1 < w) return h;	int l1 = f[cur].l, r1 = f[cur].r;	int mid = (l1 + r1) / 2;	h = min(h, h1);	if(l1 < h) {  //左子区间可能存在更高的 position 		int x = search(w, h, cur << 1);		h = min(h, x); 	}	if(mid + 1 < h){  //右子区间可能存在更高的 position 		int x = search(w, h, (cur << 1) + 1);		h = min(h, x);	}	return h;}void update(int h, int w, int cur){	int l = f[cur].l, r = f[cur].r;	if(l == r) {		t[cur].w -= w;		return;	}	int mid = (l + r) / 2;	if(h <= mid) update(h, w, cur << 1);	else update(h, w, (cur << 1) + 1);	int ll = cur << 1, rr = (cur << 1) + 1;	if(t[ll].w >= t[rr].w) {		t[cur].w = t[ll].w;		t[cur].h = t[ll].h;	}	else {		t[cur].w = t[rr].w;		t[cur].h = t[rr].h;	}}int main(){	while(scanf("%d%d%d", &H, &W, &N) == 3){		H = min(H, 200000);		Build(1, H, 1);		int x;		for(int i = 0; i < N; ++i){			scanf("%d", &x);			int ans = search(x, inf, 1);			if(ans == inf) PRintf("-1/n");			else {				printf("%d/n", ans);				update(ans, x, 1);			}		}	}	return 0;}如有不当之处欢迎指出！