題意：有一塊木板，木板的長和寬分別是h，w(1 <= h, w <= 10^9)，現(xiàn)在有n（1 <= n <= 200000）個公告要放在木板上面，規(guī)定：木板必須竟可能往上面放，如果同一行有多個可選位置，盡量往左放，如果沒有位置放置該公告輸出 ' -1',否則輸出該公告放置的高度。

  分析：共有n個公告，最多放置n行，當(dāng)h >= n時根本不可能會有公告放在上面，所有以高度的區(qū)間作為線段樹節(jié)點，節(jié)點存儲該高度區(qū)間內(nèi)的寬度最大值，以及該寬度所在的高度：

struct node{	int h, w; //寬度最大的 position}t[maxn];初始時，每個區(qū)間的最大值就是木板的寬度，每次放入一個公告，找到其放置的高度，并更新所有包含該高度的區(qū)間的最大值即可。
查詢時，應(yīng)當(dāng)向可能出現(xiàn)比當(dāng)前高度h更小的高度的區(qū)間搜索。如果當(dāng)前區(qū)間的最大寬度都無法插入公告，就退出搜索。
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{ //擔(dān)心內(nèi)存撐不住，另開的數(shù)組	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應(yīng)該放置的位置 	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) {  //左子區(qū)間可能存在更高的 position 		int x = search(w, h, cur << 1);		h = min(h, x); 	}	if(mid + 1 < h){  //右子區(qū)間可能存在更高的 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;}如有不當(dāng)之處歡迎指出！