hdu-2795 Billboard---线段树

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2795

题目大意：

一个h*w的公告牌，要在其上贴公告。

输入的是1*wi的w值，这些是公告的尺寸
接下来要满足的条件有：1、尽量往上，同一高度尽量靠左。2、求第n个广告所在的行数。3、没有合适的位置贴了则输出-1。

解题思路：

建立线段树，每一位存当前还有多少空余位置，最初时均为w，还需要优化h，当h > n时一定可以在n行放，此时h = n。

每次查询最左端大于当前wi的位置下标，放入后更新线段树

 1 #include<bits/stdc++.h>
 2 #define MID(l, r) (l + (r - l) / 2)
 3 #define lson(o) (o * 2)
 4 #define rson(o) (o * 2 + 1)
 5 using namespace std;
 6 typedef long long ll;
 7 const int INF = 1e9 +7;
 8 const int maxn = 1e6 + 10;
 9 int  h, w, n;
10 struct node
11 {
12     int l, r, mmax;
13 }tree[maxn];
14 void build(int o, int l, int r)
15 {
16     tree[o].l = l, tree[o].r = r;
17     if(l == r)
18     {
19         tree[o].mmax = w;
20         return;
21     }
22     int m = MID(l, r);
23     int lc = lson(o), rc = rson(o);
24     build(lc, l, m);
25     build(rc, m + 1, r);
26     tree[o].mmax = max(tree[lc].mmax, tree[rc].mmax);
27 }
28 //单点更新，a[p] += v;
29 int p, v;
30 void update(int o)
31 {
32     if(tree[o].l == tree[o].r)
33     {
34         tree[o].mmax += v;
35         return;
36     }
37     int m = MID(tree[o].l, tree[o].r);
38     int lc = lson(o), rc = rson(o);
39     if(p <= m)update(lc);
40     else update(rc);
41     tree[o].mmax = max(tree[lc].mmax, tree[rc].mmax);
42 }
43 int x;//查询最左端大于等于x的元素下标
44 int query(int o)
45 {
46     if(tree[o].l == tree[o].r)return tree[o].l;
47     int lc = lson(o), rc = rson(o);
48     if(tree[lc].mmax >= x)
49         return query(lc);
50     else return query(rc);
51 }
52 
53 int main()
54 {
55     int n, m;
56     while(scanf("%d%d%d", &h, &w, &n) != EOF)
57     {
58         h = min(h, n);
59         build(1, 1, h);
60         while(n--)
61         {
62             scanf("%d", &x);
63             if(x > tree[1].mmax)
64                 printf("-1
");
65             else
66             {
67                 int ans = query(1);
68                 printf("%d
", ans);
69                 p = ans;
70                 v = -x;
71                 update(1);
72             }
73         }
74     }
75     return 0;
76 }