题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795
题意：w*h的公告板要贴公告，公告是w*1的，每个公告有先后顺序，要使每个公告贴的位置尽可能地高，问每个公告最高贴多高。不能贴就输出-1。特别“不”需要注意的是，题目给的n数据范围很大，但是n只有200000。所以说可以不用关心h的范围。
线段树叶子节点维护公告板行的剩余宽度，尽可能地往左子树走。更新在查询的时候完成，不要忘记向上更新线段树。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 #define fr first 23 #define sc second 24 #define pb(a) push_back(a) 25 #define Rint(a) scanf("%d", &a) 26 #define Rll(a) scanf("%I64d", &a) 27 #define Rs(a) scanf("%s", a) 28 #define Fread() freopen("in", "r", stdin) 29 #define Fwrite() freopen("out", "w", stdout) 30 #define Rep(i, n) for(int i = 0; i < (n); i++) 31 #define For(i, a, n) for(int i = (a); i < (n); i++) 32 #define Cls(a) memset((a), 0, sizeof(a)) 33 #define Full(a) memset((a), 0w7f7f, sizeof(a)) 34 35 #define lrt rt << 1 36 #define rrt rt << 1 | 1 37 const int mawn = 2222221; 38 int sum[mawn<<1]; 39 int w, h, n, t; 40 41 void pushUP(int rt) { 42 sum[rt] = max(sum[lrt], sum[rrt]); 43 } 44 45 void build(int l, int r, int rt) { 46 sum[rt] = w; 47 if(l == r) return; 48 int m = (l + r) >> 1; 49 build(l, m ,lrt); 50 build(m+1, r, rrt); 51 // pushUP(rt); 52 } 53 54 void update(int p, int w, int l, int r, int rt) { 55 if(l == r) { 56 sum[rt] -= w; 57 return; 58 } 59 int m = (l + r) >> 1; 60 if(p <= m) update(p, w, l, m, lrt); 61 else update(p, w, m+1, r, rrt); 62 pushUP(rt); 63 } 64 65 int query(int l, int r, int rt, int w) { 66 if(l == r) { 67 sum[rt] -= w; 68 // update(l, w, 1, n, 1); 69 return l; 70 } 71 int m = (l + r) >> 1; 72 int ret = sum[rt<<1] >= w ? query(l, m, lrt, w) : query(m+1, r, rrt, w); 73 pushUP(rt); 74 return ret; 75 } 76 77 int main() { 78 // Fread(); 79 while(~scanf("%d%d%d", &h, &w, &n)) { 80 h = min(h, n); 81 build(1, h, 1); 82 while(n--) { 83 Rint(t); 84 if(sum[1] < t) printf("-1 "); 85 else printf("%d ", query(1, h, 1, t)); 86 } 87 } 88 return 0; 89 }